1. Toy模板网首页
  2. > Toy博客

算法刷题-哈希表-四数之和

9月前 作者：糖果店的幽灵 分类：Toy博客 阅读(81) 违法举报

这篇具有很好参考价值的文章主要介绍了算法刷题-哈希表-四数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一样的道理，能解决四数之和
那么五数之和、六数之和、N数之和呢？

第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]
]

思路

四数之和，和[15.三数之和]是一个思路，都是使用双指针法, 基本解法就是在[15.三数之和 的基础上再套一层for循环。

但是有一些细节需要注意，例如： 不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

[15.三数之和]的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n2)，四数之和的时间复杂度是O(n3) 。

那么一样的道理，五数之和、六数之和等等都采用这种解法。

对于15.三数之和双指针法就是将原本暴力O(n3)的解法，降为O(n2)的解法，四数之和的双指针解法就是将原本暴力O(n4)的解法，降为O(n3)的解法。

之前我们讲过哈希表的经典题目：454.四数相加II，相对于本题简单很多，因为本题是要求在一个集合中找出四个数相加等于target，同时四元组不能重复。

而454.四数相加II是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！

我们来回顾一下，几道题目使用了双指针法。

双指针法将时间复杂度：O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：

  • 27.移除元素
  • 15.三数之和
  • 18.四数之和

链表相关双指针题目：

  • 206.反转链表
  • 19.删除链表的倒数第N个节点
  • 面试题 02.07. 链表相交
  • 142题.环形链表II

双指针法在字符串题目中还有很多应用，后面还会介绍到。

C++代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[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 ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对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;
    }
};

补充

二级剪枝的部分：

if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
    break;
}

可以优化为：

if (nums[k] + nums[i] > target && nums[i] >= 0) {
    break;
}

因为只要 nums[k] + nums[i] > target，那么 nums[i] 后面的数都是正数的话，就一定 不符合条件了。

不过这种剪枝 其实有点 小绕，大家能够理解 文章给的完整代码的剪枝 就够了。

其他语言版本

Java：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {
		
            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }
		
            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
		    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Python：

# 双指针法
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):   
            if i > 0 and nums[i] == nums[i - 1]: continue  # 对nums[i]去重
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue  # 对nums[k]去重
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
			# 对nums[p]和nums[q]去重
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res

# 哈希表法
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # use a dict to store value:showtimes
        hashmap = dict()
        for n in nums:
            if n in hashmap:
                hashmap[n] += 1
            else: 
                hashmap[n] = 1
        
        # good thing about using python is you can use set to drop duplicates.
        ans = set()
        # ans = []  # save results by list()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    val = target - (nums[i] + nums[j] + nums[k])
                    if val in hashmap:
                        # make sure no duplicates.
                        count = (nums[i] == val) + (nums[j] == val) + (nums[k] == val)
                        if hashmap[val] > count:
                          ans_tmp = tuple(sorted([nums[i], nums[j], nums[k], val]))
                          ans.add(ans_tmp)
                          # Avoiding duplication in list manner but it cause time complexity increases
                          # if ans_tmp not in ans:  
                          #     ans.append(ans_tmp)
                        else:
                            continue
        return list(ans) 
        # if used list() to save results, just 
        # return ans

Go：

func fourSum(nums []int, target int) [][]int {
	if len(nums) < 4 {
		return nil
	}
	sort.Ints(nums)
	var res [][]int
	for i := 0; i < len(nums)-3; i++ {
		n1 := nums[i]
		// if n1 > target { // 不能这样写,因为可能是负数
		// 	break
		// }
		if i > 0 && n1 == nums[i-1] {  // 对nums[i]去重
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			n2 := nums[j]
			if j > i+1 && n2 == nums[j-1] {  // 对nums[j]去重
				continue
			}
			l := j + 1
			r := len(nums) - 1
			for l < r {
				n3 := nums[l]
				n4 := nums[r]
				sum := n1 + n2 + n3 + n4
				if sum < target {
					l++
				} else if sum > target {
					r--
				} else {
					res = append(res, []int{n1, n2, n3, n4})
					for l < r && n3 == nums[l+1] { // 去重
						l++
					}
					for l < r && n4 == nums[r-1] { // 去重
						r--
					}
					// 找到答案时,双指针同时靠近
					r--
					l++
				}
			}
		}
	}
	return res
}

javaScript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    const len = nums.length;
    if(len < 4) return [];
    nums.sort((a, b) => a - b);
    const res = [];
    for(let i = 0; i < len - 3; i++) {
        // 去重i
        if(i > 0 && nums[i] === nums[i - 1]) continue;
        for(let j = i + 1; j < len - 2; j++) {
            // 去重j
            if(j > i + 1 && nums[j] === nums[j - 1]) continue;
            let l = j + 1, r = len - 1;
            while(l < r) {
                const sum = nums[i] + nums[j] + nums[l] + nums[r];
                if(sum < target) { l++; continue}
                if(sum > target) { r--; continue}
                res.push([nums[i], nums[j], nums[l], nums[r]]);
		
		// 对nums[left]和nums[right]去重
                while(l < r && nums[l] === nums[++l]);
                while(l < r && nums[r] === nums[--r]);
            }
        } 
    }
    return res;
};

TypeScript：

function fourSum(nums: number[], target: number): number[][] {
    nums.sort((a, b) => a - b);
    let first: number = 0,
        second: number,
        third: number,
        fourth: number;
    let length: number = nums.length;
    let resArr: number[][] = [];
    for (; first < length; first++) {
        if (first > 0 && nums[first] === nums[first - 1]) {
            continue;
        }
        for (second = first + 1; second < length; second++) {
            if ((second - first) > 1 && nums[second] === nums[second - 1]) {
                continue;
            }
            third = second + 1;
            fourth = length - 1;
            while (third < fourth) {
                let total: number = nums[first] + nums[second] + nums[third] + nums[fourth];
                if (total === target) {
                    resArr.push([nums[first], nums[second], nums[third], nums[fourth]]);
                    third++;
                    fourth--;
                    while (nums[third] === nums[third - 1]) third++;
                    while (nums[fourth] === nums[fourth + 1]) fourth--;
                } else if (total < target) {
                    third++;
                } else {
                    fourth--;
                }
            }
        }
    }
    return resArr;
};

PHP:

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[][]
     */
    function fourSum($nums, $target) {
        $res = [];
        sort($nums);
        for ($i = 0; $i < count($nums); $i++) {
            if ($i > 0 && $nums[$i] == $nums[$i - 1]) {
                continue;
            }
            for ($j = $i + 1; $j < count($nums); $j++) {
                if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) {
                    continue;
                }
                $left = $j + 1;
                $right = count($nums) - 1;
                while ($left < $right) {
                    $sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
                    if ($sum < $target) {
                        $left++;
                    }
                    else if ($sum > $target) {
                        $right--;
                    }
                    else {
                        $res[] = [$nums[$i], $nums[$j], $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;
    }
}

Swift:

func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
    var res = [[Int]]()
    var sorted = nums
    sorted.sort()
    for k in 0 ..< sorted.count {
        // 这种剪枝不行,target可能是负数
//            if sorted[k] > target {
//                return res
//            }
        // 去重
        if k > 0 && sorted[k] == sorted[k - 1] {
            continue
        }
        
        let target2 = target - sorted[k]
        for i in (k + 1) ..< sorted.count {
            if i > (k + 1) && sorted[i] == sorted[i - 1] {
                continue
            }
            var left = i + 1
            var right = sorted.count - 1
            while left < right {
                let sum = sorted[i] + sorted[left] + sorted[right]
                if sum < target2 {
                    left += 1
                } else if sum > target2 {
                    right -= 1
                } else {
                    res.append([sorted[k], sorted[i], sorted[left], sorted[right]])
                    while left < right && sorted[left] == sorted[left + 1] {
                        left += 1
                    }
                    while left < right && sorted[right] == sorted[right - 1]  {
                        right -= 1
                    }
                    // 找到答案 双指针同时收缩
                    left += 1
                    right -= 1
                }
            }
        }
    }
    return res
}

C#:

public class Solution
{
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
        var result = new List<IList<int>>();

        Array.Sort(nums);

        for (int i = 0; i < nums.Length - 3; i++)
        {
            int n1 = nums[i];
            if (i > 0 && n1 == nums[i - 1])
                continue;

            for (int j = i + 1; j < nums.Length - 2; j++)
            {
                int n2 = nums[j];
                if (j > i + 1 && n2 == nums[j - 1])
                    continue;

                int left = j + 1;
                int right = nums.Length - 1;

                while (left < right)
                {
                    int n3 = nums[left];
                    int n4 = nums[right];
                    int sum = n1 + n2 + n3 + n4;

                    if (sum > target)
                    {
                        right--;
                    }
                    else if (sum < target)
                    {
                        left++;
                    }
                    else
                    {
                        result.Add(new List<int> { n1, n2, n3, n4 });

                        while (left < right && nums[left] == n3)
                        {
                            left++;
                        }

                        while (left < right && nums[right] == n4)
                        {
                            right--;
                        }
                    }
                }
            }
        }

        return result;
    }
}

Rust:

use std::cmp::Ordering;
impl Solution {
    pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut nums = nums;
        nums.sort();
        let len = nums.len();
        for k in 0..len {
            // 剪枝
            if nums[k] > target && (nums[k] > 0 || target > 0) { break; }
            // 去重
            if k > 0 && nums[k] == nums[k - 1] { continue; }
            for i in (k + 1)..len {
                // 剪枝
                if nums[k] + nums[i] > target && (nums[k] + nums[i] >= 0 || target >= 0) { break; }
                // 去重
                if i > k + 1 && nums[i] == nums[i - 1] { continue; }
                let (mut left, mut right) = (i + 1, len - 1);
                while left < right {
                    match (nums[k] + nums[i] + nums[left] + nums[right]).cmp(&target){
		        Ordering::Equal => {
			    result.push(vec![nums[k], nums[i], nums[left], nums[right]]);
			    left += 1;
			    right -= 1;
			    while left < right && nums[left] == nums[left - 1]{
			        left += 1;
			    }
			    while left < right && nums[right] == nums[right + 1]{
			        right -= 1;
			    }
			}
			Ordering::Less => {
			    left +=1;
			},
			Ordering::Greater => {
			    right -= 1;
			}
		    }
                }
            }
        }
        result
    }
}

Scala:文章来源地址https://www.toymoban.com/news/detail-488708.html

object Solution {
  // 导包
  import scala.collection.mutable.ListBuffer
  import scala.util.control.Breaks.{break, breakable}
  def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
    val res = ListBuffer[List[Int]]()
    val nums_tmp = nums.sorted // 先排序
    for (i <- nums_tmp.indices) {
      breakable {
        if (i > 0 && nums_tmp(i) == nums_tmp(i - 1)) {
          break // 如果该值和上次的值相同，跳过本次循环，相当于continue
        } else {
          for (j <- i + 1 until nums_tmp.length) {
            breakable {
              if (j > i + 1 && nums_tmp(j) == nums_tmp(j - 1)) {
                break // 同上
              } else {
                // 双指针
                var (left, right) = (j + 1, nums_tmp.length - 1)
                while (left < right) {
                  var sum = nums_tmp(i) + nums_tmp(j) + nums_tmp(left) + nums_tmp(right)
                  if (sum == target) {
                    // 满足要求，直接加入到集合里面去
                    res += List(nums_tmp(i), nums_tmp(j), nums_tmp(left), nums_tmp(right))
                    while (left < right && nums_tmp(left) == nums_tmp(left + 1)) left += 1
                    while (left < right && nums_tmp(right) == nums_tmp(right - 1)) right -= 1
                    left += 1
                    right -= 1
                  } else if (sum < target) left += 1
                  else right -= 1
                }
              }
            }
          }
        }
      }
    }
    // 最终返回的res要转换为List，return关键字可以省略
    res.toList
  }
}

到了这里，关于算法刷题-哈希表-四数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C++刷题第六天 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

    C++刷题第六天 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

    给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足： 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 这个题目是哈希表应用的经典题目。 如果用暴力解法，四个数组，那肯定要四层for循环嵌套，时间复杂度就是n的四次方

    2024年02月13日
    浏览(45)

  • 代码随想录-哈希表02 第454题.四数相加II&383. 赎金信&第15题. 三数之和&第18题. 四数之和

    第454题.四数相加II 第454题.四数相加II 条件：四个数组中分别取一个，相加和为0，求满足条件的元组个数 思路使用1个map，mapA保存 s1 s2中相加和及其出现次数 遍历s3 s4，去判断是否满足 0 - (s3[i] + s4[j]) 在mapA中，并统计出现次数 383. 赎金信 383. 赎金信 题目要求，s1 是否能由s

    2024年02月12日
    浏览(41)
  • 【算法】排序+双指针——leetcode三数之和、四数之和

    【算法】排序+双指针——leetcode三数之和、四数之和

    三数之和 （1）排序+双指针   算法思路： 和之前的两数之和类似，我们对暴力枚举进行了一些优化，利用了 排序+双指针 的思路：   我们先排序，然后固定⼀个数 a ，接着我们就可以在这个数后面的区间内，使用之前两数之和使用的算法，快速找到两个数之和和固定的

    2024年02月13日
    浏览(50)
  • 【算法挨揍日记】day04——15. 三数之和、18. 四数之和

    【算法挨揍日记】day04——15. 三数之和、18. 四数之和

      15. 三数之和 https://leetcode.cn/problems/3sum/ 给你一个整数数组  nums  ，判断是否存在三元组  [nums[i], nums[j], nums[k]]  满足  i != j 、 i != k  且  j != k  ，同时还满足  nums[i] + nums[j] + nums[k] == 0  。请你返回所有和为  0  且不重复的三元组。 注意： 答案中不可以包含重复的三元

    2024年02月09日
    浏览(53)
  • 【算法专题突破】双指针 - 四数之和（8）

    【算法专题突破】双指针 - 四数之和（8）

    目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后： 题目链接：18. 四数之和 - 力扣（Leetcode）  这道题跟三数之和也是一样的， 题目很好理解，就是四个数的和等于target的情况， 且这四个数不能重复。 首先还是暴力解法： 排序 + 暴力枚举 + set去重 我们当然是用优化的解法

    2024年02月09日
    浏览(36)
  • 【算法专题--双指针算法】leecode-15.三数之和（medium）、leecode-18. 四数之和（medium）

    【算法专题--双指针算法】leecode-15.三数之和（medium）、leecode-18. 四数之和（medium）

    🍁你好，我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ，故事既有了开头，就要画上一个完美的句号，让我们一起加油 双指针 常见的双指针有两种形式，一种是对撞指针，⼀种是左右指针。 对撞指针：一般用于顺序结构中

    2024年04月09日
    浏览(46)
  • leetcode刷题（字符串相加、包含每个查询的最小区间、模拟行走机器人、环形子数组的最大和、满足不等式的最大值、四数之和、树中距离之和）

    leetcode刷题（字符串相加、包含每个查询的最小区间、模拟行走机器人、环形子数组的最大和、满足不等式的最大值、四数之和、树中距离之和）

    目录 1、字符串相加 2、包含每个查询的最小区间 3、模拟行走机器人 4、环形子数组的最大和 5、满足不等式的最大值 6、四数之和 7、 树中距离之和

    2024年02月10日
    浏览(44)
  • 力扣精选算法100题——四数之和(双指针专题）

    力扣精选算法100题——四数之和(双指针专题）

    上一篇讲到（俩数之和and三数之和）这一篇我要来解析四数之和，四数之和建立在三数之和的基础上，我们需要熟练掌握三数之和的算法原理，如果大家三数之和还没弄清楚，请点击三数之和and二数之和链接即可看到。  三数之和和四数之和的题意其实都一样。 找到出四个数

    2024年01月19日
    浏览(42)

  • day7 四数相加 赎金信 三数之和 四数之和

    - 四数相加      - 不用去重，所以简单遍历就是     - 四个数，如果四重循环，就是O n^4，反正求和相加有几组数而已，俩俩一组先加起来，前俩个用map记下来，key是加和，value是出现组次数，再遍历第三、四个数组，找加和为0的，int ret = 0，去加上记录次数就好了 - 赎金信

    2024年02月14日
    浏览(90)
  • day07 四数相加Ⅱ 赎金信 三数之和 四数之和

    day07 四数相加Ⅱ 赎金信 三数之和 四数之和

    题目链接：454 四数相加Ⅱ 题意 4个整数数组nums1， nums2， nums3， nums4的长度均为n，有多少个元组（i，j，k，l）使得 nums[i]+nums[j]+nums[k]+nums[l]==0    （本题不包含去重的逻辑，i，j，k，l  可以相等，一组元素与一组元素之间的各个元素也可以相等） 暴力解法 会报如下超时错

    2024年01月24日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包