[LeetCode]15. 3Sum三数之和

超、凢脫俗 2022-10-02 14:57 140阅读 0赞

Given an array `nums` of *n* integers, are there elements *a*, *b*, *c* in `nums` 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.

**Example:**

Given array nums = [-1, 0, 1, 2, -1, -4],
    
    A solution set is:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]
    
    题目要求三数之和，跟之前的两数之和很像，但是加了一点要求，需要求出所有情况并且不能重复
    假如没有后面的要求，我们可以按照两数和的做法模仿，先遍历数组，每次选取一个nums[i],剩下的两个数的和就必须是target-nums[i]
    然后再按照两数和的做法让来求结果，相当于把三数和的问题转化成了两数和。时间复杂度从O(n)变成了O（n^2）
    但是题目加了别的条件，要求我们求出所有的情况并且不能重复，我们可以在之前的方法上做一点变化来解决
    
    首先还是类似的，把题目转化成2个数的和，我们还是先选取一个nums[i]，然后剩下的2个数的和就需要是target-nums[i]，
    之前我们的做法是使用HashMap,这次我们使用双指针来操作，这里的原因是target是固定的，永远是0，我们可以先对nums进行排序，
    排序完成后nums[i]按从小到大排列，tag=target-nums[i]，现在用2个分别指向首尾的指正k,j，使得nums[j]+nums[k]=tag
    如果nums[j]+nums[k]>tag，说明尾部的元素过大，需要缩小，就k--
    如果nums[j]+nums[k]<tag，说明首部元素小了，需要增大，就j++
    否则就是我们需要的情况。
    同时我们需要防止重复元素的情况，比如[-1,0,1,1]，这里前后2个1都是满足请款的答案，但是我们只需要一个，所以我们做去重
    while(j<k&&nums[j]==nums[j+1])j++
    while(j<k&&nums[k]==nums[k-1])k--

class Solution {
           
        public List<List<Integer>> threeSum(int[] nums) {
           
            Arrays.sort(nums);    
            List<List<Integer>> res=new ArrayList<>();
            int len=nums.length;       
            if(len==0 || nums[0]>0 || nums[len-1]<0) return res;            
            for(int i=0;i<len;i++) {
           
                if (nums[i] > 0) break;
                if (i>0 && nums[i]==nums[i-1]) continue;
                int val=0-nums[i];
                int j=i+1,k=len-1;
                while(j<k) {
           
                    if (nums[j] + nums[k] == val) {
           
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        res.add(list);
                        while (j<k && nums[j] == nums[j + 1]) j++;
                        while (j<j && nums[k] == nums[k - 1]) k--;
                        j++;
                        k--;
                    } else if (nums[j]+nums[k] < val) j++;
                    else k--;
                }
            }
            
            return res;
        }
    }

去重的方法当然还包括set，但是set需要创建对象还需要在转换回list，太消耗时间了，所以我这里没有使用

转载于:https://www.cnblogs.com/jchen104/p/10220155.html