四数之和__牛客网

唐氏综合征

这道题使用的是双层循环确定前两个数的随机性，再使用双指针+贪心算法（水桶问题）来确定后两个数的随机性，具体的说：

1. 先排序（为了后续两个数的寻找使用贪心算法）

2. 使用两个for循环确认前两个数

3. 在内层循环中，使用两个指针确认后两个数，并且尽可能让这四个数等于目标值，并跳开重复元素，如果小于目标值，左指针右移，大于目标值则右指针左移，直到找到目标值，代码比较清晰易懂，注意 List 的对象比较方式，只能用 equals,因为地址不一样：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @param target int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> fournumber (ArrayList<Integer> nums,
            int target) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int len = nums.size();

        if (len < 4) {
            return res;
        }

        // 先对数组进行排序
        Collections.sort(nums);

        for (int first = 0; first < len - 3; first++) {
            // 跳过重复元素
            if (first > 0 && nums.get(first).equals(nums.get(first - 1))) {
                continue;
            }
            for (int second = first + 1; second < len - 2; second++) {
                // 跳过重复元素
                if (second > first + 1 && nums.get(second).equals(nums.get(second - 1)))
                    continue;

                int third = second + 1;
                int fourth = len - 1;
                while (third < fourth) {
                    int sum = nums.get(first) + nums.get(second) + nums.get(third) + nums.get(
                                  fourth);
                    if (sum == target) {
                        res.add(new ArrayList<>(Arrays.asList(nums.get(first), nums.get(second),
                                                              nums.get(third), nums.get(fourth))));
                        // 跳过重复元素
                        while (third < fourth && nums.get(third).equals(nums.get(third + 1))) {
                            third++;
                        }
                        // 跳过重复元素
                        while (third < fourth && nums.get(fourth).equals(nums.get(fourth - 1))) {
                            fourth--;
                        }
                        third++;
                        fourth--;
                    } else if (sum < target) {
                        third++;
                    } else {
                        fourth--;
                    }
                }
            }
        }
        return res;
    }
}

发表于 2024-05-07 14:54:28 回复(0)

Java

被致盲的小李青

通过这道题复习了一个知识点，list.get获取的值不能用==比较，因为是包装类型所以要用equals比较

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @param target int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public  ArrayList<ArrayList<Integer>> fournumber(ArrayList<Integer> nums,
            int target) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (nums.size() < 4) {
            return res;
        }
        Collections.sort(nums);
        int n = nums.size();
        for (int i = 0; i < n - 3; i++) {
            //对第一个数进行去重
            if (i > 0 && nums.get(i).equals(nums.get(i - 1))) {
                continue;
            }
            //直至四数之和大于target还没有找到结果，就停止遍历
            if ((long) nums.get(i) + nums.get(i + 1) + nums.get(i + 2) + nums.get(
                        i + 3) > target) {
                break;
            }
            //找到与最大的三个数的四数之和大于target的，根据这个区间寻找符合条件的组
            if ((long) nums.get(i) + nums.get(n - 1) + nums.get(n - 2) + nums.get(
                        n - 3) < target) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                //第二个数原理相同
                if (j > i + 1 && nums.get(j).equals(nums.get(j - 1))) {
                    continue;
                }
                if ((long) nums.get(i) + nums.get(j) + nums.get(j + 1) + nums.get(
                            j + 2) > target) {
                    break;
                }
                if ((long) nums.get(i) + nums.get(j) + nums.get(n - 1) + nums.get(
                            n - 2) < target) {
                    continue;
                }
                //双指针遍历存在区间
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums.get(i) + nums.get(j) + nums.get(left) + nums.get(right);
                    //双指针遍历找到满足条件的组
                    //防止所有元素相同
                    if (sum == target) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(nums.get(i));
                        list.add(nums.get(j));
                        list.add(nums.get(left));
                        list.add(nums.get(right));
                        res.add(list);
                        //left和right去重，同时由于left和right的值已经加入集合，需要额外移动一次指针，找到新值
                        while (left < right && nums.get(left).equals(nums.get(left + 1))) {
                            left++;
                        }
                        left++;
                        while (left < right && nums.get(right).equals(nums.get(right - 1))) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

发表于 2022-09-13 11:31:27 回复(0)

Python2

菜鸡升职记

# -*- 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

发表于 2022-06-23 10:37:53 回复(0)

Go

小谷围做题家

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
}

发表于 2023-03-29 10:36:42 回复(0)

空中转体一周半

思路和三数之和相同。

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;
    }
}

发表于 2023-02-21 17:30:04 回复(0)

Javascript

喜欢睡觉。

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;
}

发表于 2022-06-04 19:07:05 回复(0)

牛啊牛の

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;
    }
};

发表于 2022-05-11 13:26:27 回复(0)

C++

等一个offer！

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;
    }
};

发表于 2022-05-10 20:56:26 回复(0)

四数之和

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题