42.leetcode18

42.leetcode18_4sum

1.题目描述

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

2.题目分析

先记录每两个数相加所得和及下标（放到字典中），然后再重复一次操作。不同于2Sum与3Sum，这个题不适用线性时间算法，因为无法先固定某一个元素。

3.解题思路

 1 class Solution(object):
 2     def fourSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[List[int]]
 7         """
 8         nums.sort() #排序是为了便于结果中的四个数字顺序排列
 9         result=[]
10         dic={}
11         for i in range(0,len(nums)-1):
12             for j in range(i+1,len(nums)):
13                 num=nums[i]+nums[j] #两两数字求和
14                 if num in dic: #字典dic中有num，添加值
15                     dic[num].append([i,j])
16                 else: #没有的话，添加键-值
17                     dic[num]=[[i,j]]
18         for i in range(0,len(nums)):
19             for j in range(i+1,len(nums)-2):
20                 temp=target-nums[i]-nums[j]
21                 if temp in dic: #在字典中查找键
22                     for k in dic[temp]: #确保遍历每一个值
23                         if k[0]>j and [nums[i],nums[j],nums[k[0]],nums[k[1]]]not in result:
24                             result.append([nums[i],nums[j],nums[k[0]],nums[k[1]]])
25         return result