LeetCode[Array]---- 4Sum

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d =
target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

分析:

3Sum这类题目的升级版。题目要求给定一个数组nums,从中找到所有的不重复的四个元素a,b,c,d,使得a + b +
c + d的和等于target。

依旧是借助3Sum题目的思路。依旧是对数组进行排序,然后使用双指针进行遍历,不一样的是,对于四个元素的情况,需要在三个元素的情况之上多一层循环。

具体的,我们把排序好的数组分成三个不相交部分P1, P2,P3,从P1中选择一个元素a,从P2中选择另一个元素b,然后使用双指针由前往后和由后往前的选择元素c和d,如果a + b + c + d的和nsum等于target,则记录此时的abcd;如果nsum大于target,则右指针向左移动,减少nsum值;如果nsum小于target,那么左指针向右移动,增加nsum值。

另外,对于所有的解需要进行去重。具体可以判断每次选择的元素是否与前一次选择的元素相同,如果相同则跳过不选。

相应的代码为:

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        nums_len = len(nums)
        res = []
        for i in range(nums_len - 3):
            if i and nums[i] == nums[i - 1]:
                continue
            for j in range(i+1, nums_len - 2):
                left = j + 1
                right = nums_len - 1
                if j != i + 1 and nums[j] == nums[j-1]:
                    continue
                while left < right:
                    nsums = nums[i] + nums[j] + nums[left] + nums[right]
                    if nsums == target:
                        res.append([nums[i], nums[j], nums[left], nums[right]])
                        while left < right and nums[left+1] == nums[left]:
                            left += 1
                        while left < right and nums[right-1] == nums[right]:
                            right -= 1
                        left += 1
                        right -= 1
                    elif nsums > target:
                        right -= 1
                    else:
                        left += 1
        return res
时间: 04-17

LeetCode[Array]---- 4Sum的相关文章

LeetCode 017 4Sum

[题目] Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet (a,b,c,d) must be in non-descending o

LeetCode[Array]: Rotate Image

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? 参考LeetCode[Array]: Spiral Matrix II的迭代思路,先完成最外环的旋转,然后依次旋转内环.我的C++代码如下: void rotate(vector<vector<int> >

[LeetCode] 018. 4Sum (Medium) (C++/Java/Python)

索引:[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql) Github: https://github.com/illuz/leetcode 018.4Sum (Medium) 链接: 题目:https://oj.leetcode.com/problems/4sum/ 代码(github):https://github.com/illuz/leetcode 题意: 给一个数列 S ,找出四个数 a,b,c,d 使得a + b + c + d = targ

LeetCode[Array]: Pascal&#39;s Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space? 这个问题比较简单. vector<int> getRow(int rowIndex) { vector<int> row, prev

LeetCode[Array]: Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 这个题目跟LeetCode[Array]: Spiral Matrix不同的是:这个题目并不

[LeetCode] 454. 4Sum II 四数之和II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero. To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the r

Array + two points leetcode.18 - 4Sum

题面 Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b+ c + d = target? Find all unique quadruplets in the array which gives the sum of target. 给定无序数组,找到和为target的不重复的长度为4的子序列 样例 1. Given

[LeetCode] 18. 4Sum ☆☆

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For exampl

【Leetcode】4Sum

题目链接:https://leetcode.com/problems/4sum/ 题目: Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadrupl