数组类15--三数之和（M）

image.png

AC代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return ans;
        }
        Arrays.sort(nums);
        int len = nums.length;
        //impossible
        if(nums[0] > 0 || nums[len - 1] < 0) {
            return ans;
        }
        for(int i = 0; i < len; i++) {
            //impossible
            if(nums[i] > 0) {
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = nums[i];
            //two pointers
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                if(nums[left] + nums[right] + target == 0) {
                    List<Integer> item = new ArrayList<>();
                    item.add(target);
                    item.add(nums[left]);
                    item.add(nums[right]);
                    ans.add(item);
                    int tmpLeft = nums[left];
                    int tmpRight = nums[right];
                    while(left < right && tmpLeft == nums[left] && tmpRight == nums[right]) {
                        left++;
                        right--;
                    }
                    continue;
                }else if(nums[left] + nums[right] + target < 0) {
                    left++;
                }else {
                    right--;
                }
            }
            
        }
        return ans;
    }
}

精髓

1. 转化为双指针，a+b = 0转化为a+b = -c，n方复杂度
2. 排除不可能情况：比如，排序后首个大于0，不可能，最后一个小于0，也不可能
3. 去重，外层循环过程中，当前值跟上一个一样，没必要再继续。
   首次没有AC原因：
   -2, 0, 0, 2, 2这种情况，-2,0,2之后，左右指针分别指向0和2，left++和right--后还是0和2，应当去重。