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

```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```

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

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