【迎战蓝桥杯】 算法·每日一题（详解+多解）-- day6

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        for (int i=0; i<n-2; i++){
            if (i>0 && nums[i] == nums[i-1]) continue;

            int left = i+1;
            int right = n-1;

            while(left<right){
                int cur = nums[i] + nums[left] + nums[right];
                if (cur<0) left++;
                else if (cur>0) right--;
                else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left<right && nums[left] == nums[left+1]) left++;
                    while (left<right && nums[right] == nums[right-1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

Arrays.sort(nums);

	class Solution {
		public List<List<Integer>> threeSum(int[] nums) {
			if (null == nums || 3 > nums.length) {
				return new ArrayList<>();
			}
			Arrays.sort(nums);
			int lastNum = Integer.MAX_VALUE;
			List<List<Integer>> result = new ArrayList<>();
			for (int i = 0; i < nums.length - 1; i++) {
				if (nums[i] == lastNum) {
					continue;
				}
				lastNum = nums[i];
				int left = i + 1;
				int right = nums.length - 1;
				int target = -nums[i];
				int sum;
				while (left < right) {
					sum = nums[left] + nums[right];
					if (sum == target) {
						result.add(Arrays.asList(lastNum, nums[left], nums[right]));
						++left;
						while(left < right && nums[left] == nums[left-1]){
							++left;
						}
						--right;
						while (left < right && nums[right] == nums[right + 1]) {
							--right;
						}
					} else if (sum > target) {
						--right;
					} else {
						++left;
					}
				}
			}
			return result;
		}
	}

vector<vector<int>> process(vector<int>&nums,int target,int i,int n){
    int left=i,right=n;
    vector<vector<int>> res;
    while(left<right){
        int temp=nums[left]+nums[right];
        int lval=nums[left],rval=nums[right];//记录当前左右指针指向的值，因为遇到重复的值这样可以直接跳过
        if(temp<target){
            while(left<right&&nums[left]==lval)left++;
        }
        if(temp>target){
            while(left<right&&nums[right]==rval)right--;
        }
        if(temp==target){
            res.push_back({nums[left],nums[right]});
            while(left<right&&nums[left]==lval)left++;
            while(left<right&&nums[right]==rval)right--;//找到目标值了，left和right也要改变，这里记录一下，因为自己经常忘
        }
    }
    return res;
}

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());//先对数组进行排序
    int n=nums.size()-1;
    vector<vector<int>> res;
    for(int i=0;i<n-1;++i){
        vector<vector<int>> temp=process(nums,0-nums[i],i+1,n);//寻找的范围是当前值后面的那个值一直到最后
        if(!temp.empty()){
            for(auto x:temp){
                x.push_back(nums[i]);
                res.push_back(x);
            }
        }
        while(i<n-1&&nums[i+1]==nums[i])i++;//这里同样用来排除重复值
    }
    return res;
}