Fork me on GitHub

18 - 四数相加

发表于 | 分类于

题目描述

我是怎么也想不出来时间复杂度小一点的方法，于是只好利用搜索引擎了。

cr:

解题思路

  1. 升序排序；
  2. 使用双层循环计算两数之和；
  3. 两指针在剩余元素中相向移动；
  4. 若四数之和等于target，加入结果序列；
  5. 跳过重复值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        nums = sorted(nums)
        l = len(nums)
        res = []

        # i1,i2,i3,i4为四个指针
        for i1 in range(0, l-3):
        	for i2 in range(i1 + 1, l-2):
        		i3 = i2 + 1
        		i4 = l - 1

        		# 循环结束条件为两指针相遇
        		while i3 < i4:
        			the_sum = nums[i1] + nums[i2] + nums[i3] + nums[i4]
        			if the_sum < target:
        				i3 += 1
        			elif the_sum > target:
        				i4 -= 1
        			else:
        				li = [ nums[i1], nums[i2], nums[i3], nums[i4] ] 
        				if li not in res:
        					res.append(li)
        				
        				i3 += 1

        return res

debug

list赋值错误

li是空数组，使用li[0]=xx这样赋值当然越界了，改用append。