Leetcode-15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法：暴力探索就不说了；1. 仍然使用类似two sum的存储机制，使用set做存储，时间复杂度为O(N2)，空间复杂度O(N)；2. 使用双指针法进行前后夹击，时间复杂度O(N2)，空间复杂度O(1)

1. using hashset

Java

class Solution {
   
    public List<List<Integer>> threeSum(int[] nums) {
   
        Arrays.sort(nums);
        // List<List<Integer>> list = new ArrayList<>();
        HashSet<List<Integer>> res = new HashSet<>();
        for(int i=0;i<nums.length-2;i++){
   
            if(i>0 && nums[i]==nums[i-1]) continue;
            HashSet<Integer> set = new HashSet<>();
            for(int j=i+1;j<nums.length;j++){
   
                if(set.contains(nums[j])){
   
                    res.add(Arrays.asList(nums[i],nums[j],-(nums[i]+nums[j])));
                }else{
   
                    set.add(-(nums[i]+nums[j]));
                }
            }
        }
        // return list.stream().distinct().collect(Collectors.toList()); // using java8 stream
        List<List<Integer>> lst = new ArrayList<>();
        lst.addAll(res); // convert set to list
        return lst;
    }
}

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = set()
        for i,v in enumerate(nums[:-2]):
            if i>0 and v==nums[i-1]:
                continue
            set1 = set()
            for j in nums[i+1:]:
                if j in set1:
                    res.add((v,j,-(v+j)))
                else:
                    set1.add(-(v+j))
        return map(list,res)

2. using double pointer

Java

class Solution {
   
    public List<List<Integer>> threeSum(int[] nums) {
   
        Arrays.sort(nums);
        List<List<Integer>> lst = new ArrayList<>();
        for(int i=0;i<nums.length-2;i++){
   
            if(i>0 && nums[i]==nums[i-1]) continue;
            int l=i+1, r=nums.length-1, target = -nums[i];
                while(r>l){
   
                    if(nums[l]+nums[r]==target){
   
                        lst.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        while(l+1<r && nums[l+1]==nums[l]) l++;
                        while(r-1>l && nums[r-1]==nums[r]) r--;
                        l++;r--;
                    }else if (nums[l]+nums[r]<target){
   
                        l++;
                    }else{
   
                        r--;
                    }
                }
        }
        return lst;
    }
}

Python

class Solution:
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if i>0 and nums[i]==nums[i-1]:
                continue
            l,r = i+1,len(nums)-1
            while l<r:
                if nums[l]+nums[r]==-nums[i]:
                    res.append([nums[l],nums[r],nums[i]])
                    while l+1<r and nums[l+1]==nums[l]:
                        l+=1
                    while r-1>l and nums[r-1]==nums[r]:
                        r-=1
                    l+=1
                    r-=1
                elif nums[l]+nums[r]>-nums[i]:
                    r -= 1
                else:
                    l+=1
        return res

Leetcode-18. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解法：可以发现这种N数之和的规律就是将N数之和转换成为（N-1）数之和，最后转换到二数之和，看起来非常适合用递归来写，所以我们直接写一个通用的解法，时间复杂度O(N^(n-1))

Java

class Solution {
   
    int len = 0;
    public List<List<Integer>> fourSum(int[] nums, int target) {
   
        this.len = nums.length;
        Arrays.sort(nums);
        return nSum(nums,target,4,0);
    }
    public ArrayList<List<Integer>> nSum(int[] nums, int target, int n,int index){
   
        ArrayList<List<Integer>> lst = new ArrayList<>();
        if(index>=this.len){
   
            return lst;
        }
        if(n==2){
   
            int l = index, r = this.len - 1;
            while(l<r){
   
                if(nums[l]+nums[r]==target){
   
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[l]);
                    tmp.add(nums[r]);
                    lst.add(tmp);
                    // lst.add(Arrays.asList(nums[l],nums[r]));
                    while(l<r && nums[l+1]==nums[l]) l++;
                    while(l<r && nums[r-1]==nums[r]) r--;
                    l++;r--;
                }else if(nums[l]+nums[r]>target){
   
                    r--;
                }else{
   
                    l++;
                }
            }
        }else{
   
            for(int i=index;i<this.len-n+1;i++){
   
                ArrayList<List<Integer>> tmp = this.nSum(nums,target-nums[i],n-1,i+1);
                if(tmp!=null){
   
                    for(List<Integer> l:tmp){
   
                        l.add(0,nums[i]);
                    }
                lst.addAll(tmp);
                while(i<this.len-1 && nums[i]==nums[i+1]) i++;
                }
            }
        }
        return lst;
    }
}

Python