四数之和

# -*- coding: utf-8 -*-

# coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param target int整型
# @return int整型二维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/d5b74806fa104518903884e182f47e35?tpId=196&tqId=40414&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D7%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        题目要求获取nums[a] + nums[b] + nums[c] + nums[d] = target的所有不同组合[nums[a], nums[b], nums[c], nums[d]]
        枚举nums[a]: # a的取值范围[a: n-3)
            对a去重
            枚举nums[b]：# b的范围[a+1: n-2)
                对b去重
                双指针c和d，在区间[b+1:n)中，寻找满足条件的组合，同时对c, d分别去重
    复杂度：
        时间复杂度：O(N^3)，N为数组nums的长度
        空间复杂度：O(N)，排序算法所需的空间复杂度
    """

    def fournumber(self, nums, target):
        # write code here
        n = len(nums)

        nums.sort()

        res = []
        for a in range(n - 3):
            if a > 0 and nums[a] == nums[a - 1]: # 对a去重，剪枝
                continue
            for b in range(a + 1, n - 2):
                if b > a + 1 and nums[b] == nums[b - 1]: # 对b去重，剪枝
                    continue
                c, d = b + 1, n - 1
                while c < d:
                    Sum = nums[a] + nums[b] + nums[c] + nums[d]
                    if Sum == target:
                        res.append([nums[a], nums[b], nums[c], nums[d]])
                        while c < d and nums[c] == nums[c + 1]: # 对c去重，剪枝
                            c += 1
                        while c < d and nums[d] == nums[d - 1]: # 对d去重，剪枝
                            d -= 1
                        c += 1
                        d -= 1
                    elif Sum > target:
                        d -= 1
                    else:
                        c += 1
        return res


if __name__ == "__main__":
    sol = Solution()

    # nums, target = [2, 0, -2, 3, -3, 0], 0

    # nums, target = [2, 0, -2, 0, 1, -3, 4, -4], -4

    nums, target = [3, 2, 4, -3, -5, -3, -2, 2, 0, 4, -3], 1

    res = sol.fournumber(nums, target)

    print res

package main
import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型二维数组
*/
func fournumber( nums []int ,  target int ) [][]int {
    ans:=[][]int{}
    sort.Ints(nums)
    for i:=0;i<len(nums);i++{
        if i>0&&nums[i]==nums[i-1]{
            continue
        }
        for j:=i+1;j<len(nums);j++{
            if j>i+1&&nums[j]==nums[j-1]{
                continue
            }
            l,r:=j+1,len(nums)-1
            for l<r{
                sum:=nums[i]+nums[j]+nums[l]+nums[r]
                if sum==target{
                    ans=append(ans,[]int{nums[i],nums[j],nums[l],nums[r]})
                    for l<r&&nums[l]==nums[l+1]{
                        l++
                    }
                    for l<r&&nums[r]==nums[r-1]{
                        r--
                    }
                    l++
                    r--
                }else if sum>target{
                    r--
                }else{
                    l++
                }
            }
        }
    }
    return ans
}

思路和三数之和相同。

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> fournumber (ArrayList<Integer> nums, int target) {
        Collections.sort(nums);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(); 
        for(int one = 0; one < nums.size() - 3; ++one) {
            for(int two = one + 1; two < nums.size() - 2; ++two) {
                int left = two + 1, right = nums.size() - 1;
                while(left < right) {
                    double temp =nums.get(left) +nums.get(right) + nums.get(one) +nums.get(two);
                    if((double)target == temp) {
                        ArrayList<Integer> templist= new ArrayList<>();
                        templist.add(nums.get(one));
                        templist.add(nums.get(two));
                        templist.add(nums.get(left));
                        templist.add(nums.get(right));
                        if(!res.contains(templist))
                            res.add(templist);
                        left++;
                    } else  if(nums.get(one) +nums.get(two) +nums.get(left) +nums.get(right) < target) {
                        left++;
                    } else right--;
                }
            }
        }
        return res;
    }
}

function fournumber( nums ,  target ) {
    // write code here
    nums.sort((a, b) => a-b);
    let res = [];
    let max = nums.length-1;
    let i = 0;
    let num1 = nums[i];
    while(i < nums.length - 3) {
        let i2 = i + 1;
        let l = i2 + 1;
        let h = max;
        while(i2 < nums.length - 2){
            let num2 = nums[i2];
            let low = nums[l];
            let high = nums[h];
            while(l < h) {
                if(num1 + num2 + low + high == target) {
                    res.push([num1, num2, low, high]);
                    while(nums[l] == low) {l++;}
                    while(nums[h] == high) {h--;}
                    low = nums[l];
                    high = nums[h];
                } else if (num1 + num2 + low + high < target) {
                    while(nums[l] == low) {l++;}
                    low = nums[l];
                } else if (num1 + num2 + low + high > target) {
                    while(nums[h] == high) {h--;}
                    high = nums[h];
                }
            }
            while(nums[i2] == num2) {i2++;}
            l = i2 + 1;
            h = max;
        }
        while(num1 == nums[i]) {i++;}
        num1 = nums[i];
    }
    return res;
}

class Solution {
public:
    vector<vector<int>> fournumber(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 这种剪枝是错误的，这道题目target 是任意值
            // if (nums[k] > target) {
            //     return result;
            // }
            // 去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
                        right--;
                        // 当前元素不合适了，可以去重
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if (nums[k] + nums[i]  < target - (nums[left] + nums[right])) {
                        left++;
                        // 不合适，去重
                        while (left < right && nums[left] == nums[left - 1]) left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }
 
            }
        }
        return result;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > fournumber(vector<int>& nums, int target) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<n;j++){
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                int k=j+1,p=n-1;
                while(k<p){
                    while(k>j+1&&k<n&&nums[k]==nums[k-1]){
                        k++;
                    }
                    if(k>=p){
                        break;
                    }
                    long sum=(long)nums[i]+nums[j]+nums[k]+nums[p];
                    if(sum==target){
                        res.push_back({nums[i],nums[j],nums[k],nums[p]});
                        k++;
                    }else if(sum>target){
                        p--;
                    }else if(sum<target){
                        k++;
                    }
                }
            }
        }
        return res;
    }
};