视频例题学习记录

https://www.bilibili.com/video/BV1bP411c7oJ

  • 视频讲了两道题，两数之和和三数之和，下意识想用的哈希表记录已遍历值从而让另一个值是否符合的判断只要O（1）的方法。但这个方法空间复杂度O（n），且很难向三数之和，四数之和推广。

  • 灵神给出了相向双指针解法，也就是首尾各一个指针。首先是需要数组有序，默认非降序排列，然后判断当前两个之和与目标的关系，比目标大说明这两个值需要小点，就要大的那个前移。小了的话，就需要小值指针后移。注意这里不同情况都只对应一种指针移动。

  • 那么对于三数之和呢？两个指针看起来不够用。确实，所以把多出来的那个放外面加一个循环处理，剩下两个还是相向双指针。

课后作业完成记录

2824. 统计和小于目标的下标对数目

https://leetcode.cn/problems/count-pairs-whose-sum-is-less-than-target/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        # 排序O nlogn，过程 O n，总共O nlogn，空间 O 1
        nums.sort()
        i = 0
        j = len(nums)-1
        ans = 0
        while i<j:
            if nums[i] + nums[j] < target:
                # print(i, j)
                ans += j-i # 满足条件的时候，i到j之间都满足条件，一次计算完
                i += 1 # 然后考虑下一个基准的情况
            else:
                j -= 1
        return ans

16. 最接近的三数之和

https://leetcode.cn/problems/3sum-closest/

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
34
35
36
37
38
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 时间：排序O nlogn，过程 n方，总共算n方；空间 O 1
        nums.sort()
        n = len(nums)
        ans = 1000000
        for i in range(n-2):
            if i>0 and nums[i]==nums[i-1]: #跳过已经算过的
                continue
            
            s = nums[i]+nums[i+1]+nums[i+2]# 最小的情况也比target大，其他情况只会更大，所以就只考虑这一种情况
            if s > target:
                if abs(ans - target) > abs(s - target):
                    ans = s 
                break # 由于i往后也只会更大，所以干脆终止
            
            s = nums[i]+nums[-2]+nums[-1]# 最大的情况也比target小，其他情况只会更小，所以就只考虑这一种情况
            if s < target:
                if abs(ans - target) > abs(s - target):
                    ans = s 
                continue

            j = i+1
            k = n-1 

            while j < k:
                s = nums[i]+nums[j]+nums[k]
                if abs(ans - target) > abs(s - target):
                    ans = s 
                
                if s == target:
                    break
                elif s > target:
                    k -= 1 
                else:
                    j += 1
        return ans

18. 四数之和

https://leetcode.cn/problems/4sum/description/

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
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        # 时间复杂度，排序 nlogn，过程是n的三次方，所以就是三次方；空间复杂度O 1
        ans = []
        nums.sort()
        n = len(nums)
        for i in range(n-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue

            # 让极大和极小的情况节省时间
                if nums[i] + nums[-3] + nums[-2] + nums[-1] < target:
                    continue
                
                if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                    break

            sub_target = target - nums[i]
            for j in range(i+1, n-2):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                
                # 让极大和极小的情况节省时间
                if nums[j] + nums[-2] + nums[-1] < sub_target:
                    continue
                
                if nums[j] + nums[j+1] + nums[j+2] > sub_target:
                    break

                p, q = j+1, n-1
                while p < q:
                    s = nums[j] + nums[p] + nums[q]
                    if s == sub_target:
                        ans.append([nums[i], nums[j], nums[p], nums[q]])
                        p += 1
                        while p<q and nums[p] == nums[p-1]:
                            p += 1
                        q -= 1
                        while p<q and nums[q] == nums[q+1]:
                            q -= 1
                    elif s > sub_target:
                        q -= 1
                    else:
                        p += 1
        return ans

611. 有效三角形的个数

https://leetcode.cn/problems/valid-triangle-number/description/ 

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 triangleNumber(self, nums: List[int]) -> int:
      # 时间复杂度，排序nlogn，过程n方，总共算n方；空间复杂度O 1
        ans = 0
        nums.sort()
        n = len(nums)
        for i in range(n-1, 1, -1):
            # i足够小，连所有最小的两个值都更大，剩下随便三个数都能是三角形
            if nums[0]+nums[1] > nums[i]:
                ans += (i+1)*i*(i-1)//6
                break
                
            # i太大了，这个循环内不可能有满足的
            if nums[i-2]+nums[i-1]<=nums[i]:
                continue 

            # 这题比较阴的一点在于，如果外层循环不定为最长边的话
            # 变动的另外两个指针的变化就会冲突
            # 比如说，此时i+j小于k（这里代指对应值），是j增加还是k减小？冲突了，并非唯一选择
            # 如果把k固定，i和j动，那么值不够就i增加，值大了j就可以减少
            j = 0
            k = i-1

            while j < k:
                # print(i, j, k)
                if nums[j]+nums[k] > nums[i]:
                    # print("ok, get", k-j)
                    ans += k-j
                    k -= 1
                else:
                    j += 1

        return ans