面试经典150题——三数之和

题目来源

力扣每日一题；题序：15

我的题解

方法一 暴力解法 超时

进行三重循环遍历，判断和是否为0，若为0，则将对应的值组合成List并加入Set。

时间复杂度：O($n^3$)
空间复杂度：O(n)

public List<List<Integer>> threeSum(int[] nums) {
    Set<List<Integer>> resSet=new HashSet<>();
    int n=nums.length;
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                if(nums[i]+nums[j]+nums[k]==0){
                    List<Integer> t=Arrays.asList(nums[i],nums[j],nums[k]);
                    t.sort((a,b)->a-b);
                    resSet.add(t);
                }
            }
        }
    }
    return new ArrayList<>(resSet);
}

方法二 扩展两数之和（双指针）

先确定一个数，然后使用两数之和的解法进行计算。注意需要去重，即在求两数之和的过程中需要将去掉重复的元素。

时间复杂度：O($n^2$)。
空间复杂度：O(n)

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res=new ArrayList<>();
    for(int i=0;i<nums.length;){
        List<List<Integer>> t=twoSum(nums,-nums[i],i);
        int pre=nums[i];
        while(i<nums.length&&nums[i]==pre)
            i++;
        res.addAll(t);
    }
    return res;
}
public List<List<Integer>> twoSum(int[] nums,int  target,int index){
    int left=index+1,right=nums.length-1;
    List<List<Integer>> res=new ArrayList<>();
    while(left<right){
        int tNum=nums[left]+nums[right];
        int preLeft=nums[left];
        int preRight=nums[right];
        if(index==left){
            left++;
            continue;
        }
        if(index==right){
            right--;
            continue;
        }
        if(tNum==target){
            List<Integer> t=Arrays.asList(-target,nums[left],nums[right]);
            res.add(t);
            while(left<right&&nums[left]==preLeft)
                left++;
            while(right>left&&nums[right]==preRight)
                right--;
        }else if(tNum<target){
            while(left<right&&nums[left]==preLeft)
                left++;
        }else{
            while(right>left&&nums[right]==preRight)
                right--;
        }
    }
    return res;
}

方法三 扩展为通用的n数之和

时间复杂度：O($n^2$)。
空间复杂度：O(n)

public List<List<Integer>> threeSum(int[] nums) {
	Arrays.sort(nums);
	List<List<Integer>> resList = nSum(nums, 0, 3, 0);
	return resList;
}

public  List<List<Integer>> nSum(int[] nums, int target, int n, int start) {
	int len = nums.length;
	List<List<Integer>> res = new ArrayList<>();
	if (n == 2) {
		int left = start, right = len - 1;
		while (left < right) {
			int temp = nums[left] + nums[right];
			int l = nums[left], r = nums[right];
			if (temp < target) {
				while (left < right && l == nums[left])
					left++;
			} else if (temp > target) {
				while (left < right && r == nums[right])
					right--;
			} else {
				List<Integer> sub = new ArrayList(Arrays.asList(nums[left], nums[right]));
				res.add(sub);
				while (left < right && l == nums[left])
					left++;
				while (left < right && r == nums[right])
					right--;
			}
	
		}
	} else {
		for (int i = start; i < len; i++) {
			List<List<Integer>> subList = nSum(nums, target - nums[i], n - 1, i + 1);
			for (List<Integer> list : subList) {
				list.add(nums[i]);
				res.add(list);
			}
			while (i < len - 1 && nums[i] == nums[i + 1])
				i++;
		}
	}
	
	return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~