leetcode 15. 3Sum 以及2Sum的问题的处理和求解

我会带着你远行 2022-06-09 06:57 170阅读 0赞

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = \[-1, 0, 1, 2, -1, -4\],

A solution set is:  
\[  
\[-1, 0, 1\],  
\[-1, -1, 2\]  
\]

这个问题很经典，对于3Sum，先确定一个数字，然后这个问题就退化成了2Sum的问题。针对2Sum，先对数组排序，然后使用双指针匹配可行解就可以解决，虽然可以考虑使用HashMap加速搜索，但是对于本题使用HashMap的与否的时间复杂度都一样，都是O(nlog(n))。可以参考这个链接：[ 求和问题总结(leetcode 2Sum, 3Sum, 4Sum, K Sum)][_leetcode 2Sum_ 3Sum_ 4Sum_ K Sum]，写的很清楚。

这里我只写了2Sum和3Sum的代码，注意要避免重复排序，同时避免重复数字的循环。

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Solution 
    {
        
        //http://blog.csdn.net/nanjunxiao/article/details/12524405
        //K sum 可以递归去做
        /*
         * 2Sum问题的求解:排序外加双指针来实现
         * */
         public List<List<Integer>> twoSum(int[] nums,int target) 
            {
                List<List<Integer>> twoResList=new ArrayList<>();
                Arrays.sort(nums);
                int i=0,j=nums.length-1;
                while(i<j)
                {
                    int sum=nums[i]+nums[j];
                    if(sum==target)
                    {
                        List<Integer> tt=new ArrayList<Integer>();
                        tt.add(nums[i]);
                        tt.add(nums[j]);
                        twoResList.add(tt);
                        //重复的数据就不在统计
                        while(i<j && nums[i]==nums[i+1]) i++;
                        while(i<j && nums[j]==nums[j-1]) j--;
                        i++;
                        j--;
                    }else if(sum <=target)
                        i++;
                    else
                        j--;
                }
                return resList;
            }
    
    
        List<List<Integer>> resList=new ArrayList<>();
        public List<List<Integer>> threeSum(int[] nums) 
        {
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++)
            {
                //重复的数据就不在统计
                if(i>=1 && nums[i]==nums[i-1])
                    continue;
                getRes(nums,i+1,-nums[i]);
            }
            return resList;
        }
    
        private void getRes(int[] nums, int beg,int target)
        {
    
            int i=beg,j=nums.length-1;
            while(i<j)
            {
                int sum=nums[i]+nums[j];
                if(sum==target)
                {
                    List<Integer> tt=new ArrayList<Integer>();
                    tt.add(-target);
                    tt.add(nums[i]);
                    tt.add(nums[j]);
                    resList.add(tt);
    
                    //重复的数据就不在统计
                    while(i<j && nums[i]==nums[i+1]) i++;
                    while(i<j && nums[j]==nums[j-1]) j--;
                    i++;
                    j--;
                }else if(sum <=target)
                    i++;
                else
                    j--;
            }
        }
    
    
    
    }

下面是C++的做法，就是转换为2Sum的问题，

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    class Solution
    {
    public:
        vector<vector<int>> threeSum(vector<int>& nums)
        {
            vector<vector<int>> res;
            sort(nums.begin(),nums.end());
            for (int i = 0; i < nums.size(); i++)
            {
                if (i >= 1 && nums[i] == nums[i - 1])
                    continue;
                dealWithTwoSum(res,nums, i + 1, -nums[i]);
            }
            return res;
        }
    
        void  dealWithTwoSum(vector<vector<int>> &res, vector<int>& nums, int beg, int target)
        {
    
            int i = beg, j = nums.size() - 1;
            while (i < j)
            {
                int sum = nums[i] + nums[j];
                if (sum == target)
                {
                    vector<int> one;
                    one.push_back(-target);
                    one.push_back(nums[i]);
                    one.push_back(nums[j]);
                    res.push_back(one);
    
                    while (i < j && nums[i] == nums[i + 1]) i++;
                    while (i < j && nums[j] == nums[j - 1]) j--;
                    i++;
                    j--;
                }
                else if (sum < target)
                    i++;
                else
                    j--;
            }
        }
    };

[_leetcode 2Sum_ 3Sum_ 4Sum_ K Sum]: http://blog.csdn.net/nanjunxiao/article/details/12524405