[LeetCode]题解（python）：018-4Sum

题目来源：

https://leetcode.com/problems/4sum/

题意分析：

这道题目和3Sum的题目类似，找出所有的4个数，使得这4个数等于target。

题目思路：

这道题做法和3Sum的一样，先排好序。固定两个数，剩下的两个数夹逼定理找出。总的时间复杂度(O(n^3))。其中可以做一些简单的优化，比如夹逼的时候，如果最小两个数之和大于target - 前两个数，或者最大的两个数之和小于target - 前两个数直接跳出。

代码（python）：

 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         size = len(nums)
 9         ans = []
10         if size < 4:
11             return ans
12         nums.sort()
13         i = 0
14         while i < size - 3:
15             j = i + 1
16             while j < size - 2:
17                 tmp = target - nums[i]- nums[j]
18                 k = j + 1
19                 t = size - 1
20                 while k < t:
21                     if nums[k] + nums[k + 1] > tmp or nums[t] + nums[t-1]< tmp:
22                         break
23                     if nums[k] + nums[t] < tmp:
24                         k += 1
25                     elif nums[k] + nums[t] > tmp:
26                         t -= 1
27                     else:
28                         ans.append([nums[i],nums[j],nums[k],nums[t]])
29                         k += 1
30                         t -= 1
31                         while k < t:
32                             if nums[k] == nums[k -1]:
33                                 k += 1
34                             if nums[t] == nums[t+1]:
35                                 t -= 1
36                             if nums[k] != nums[k - 1] and nums[t] != nums[t+1]:
37                                 break
38                 j += 1
39                 while j < size - 2:
40                     if nums[j] != nums[j - 1]:
41                         break
42                     j += 1
43             i += 1
44             while i < size - 3:
45                 if nums[i] != nums[i - 1]:
46                     break
47                 i += 1
48         return ans

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4835747.html