#Coding-Data View

数组-选择子集

常见类型

不固定个数，所有满足要求的子集 (常用回溯法)
固定个数，但是要求满足某种性质

难点：

当选定一个元素后，另一个并没有明确的顺序

不固定个数

固定个数

2元组

蛮力方法时间是O( n^2 )

561. Array Partition I

问题转换为下面的形式:

$max(\sum_{i=0}^n min(a_i, b_i) )$

如何在O(n)时间内求出？

以另一种方式解读$ min(a_i, b_i) $，可以理解为在$ a_i$,$b_i$中我们选择了较小的那一个，同时整个数组的和承受了$ |a_i - b_i| $的损失。

而这个问题就是在让这种损失最小。

167. Two Sum II - Input array is sorted

有序数组中的2Sum，有序改怎么利用？

可以用一个数组元素值到下标的map,map[A[i]] = i,当遍历到某个元素时，寻找目标值减去它的元素。（没有利用有序这一条件）

We use two indexes, initially pointing to the first and last element respectively. Compare the sum of these two elements with target. If the sum is equal to target, we found the exactly only solution. If it is less than target, we increase the smaller index by one. If it is greater than target, we decrease the larger index by one. Move the indexes and repeat the comparison until the solution is found. - Official Solution

532. K-diff Pairs in an Array

怎么不重复计算(i,j)和(j,i)？-> 排序

1010. Pairs of Songs With Total Durations Divisible by 60

把数组中的每个元素都对60取模后，就变成了2Sum的问题，目标和为60或0。

为了让0的余数也能统一处理，(60 - t % 60) % 60

1 -> 59
2 -> 58
...
0 -> 0

这里还需要注意一点的是这里不忽略重复元素，比如:[60,60,60]的结果为3。

for(auto t:time)
{
    res += c[ (60 - t % 60) % 60 ];
    c[t % 60] += 1;
}

数组c中记录了过去遇见过的key的个数，每当遇见一个t，查看之前和它互余数的个数，如果个数不为0，那么就可以和之前所有的数都能构成符合要求的pair。

1014. Best Sightseeing Pair

寻找i,j使得A[i] + A[j] + i - j最大

涉及A[i],A[j],i,j四个元素

Can you tell the best sightseeing spot in one pass (ie. as you iterate over the input?) What should we store or keep track of as we iterate to do this?

// res原来最好的结果 cur过去遇见过最好的分数
res = max(res, cur + a);
            
// cur当前最好的值
cur = max(cur, a) - 1;

3元组

蛮力方法时间是 O( n^3 )

在哪里可以节约时间？-> 排序。因为数组有序后使得2-Sum的搜索过程更有目的性。

K-Sum的问题可以转化为2-Sum问题，复杂度与K有关，一般时间复杂度为O( n^k-1 )。

比如在3-Sum问题中，要想找到符合要求的(i,j,k)，需要先固定一个元素，比如i，那么问题就转化为了目标为target-A[i]的2-Sum问题，而2-Sum可以在O( n )时间内解决，所以3-Sum可以在O( n^2 )时间内解决。

15. 3Sum

259. 3Sum Smaller

16. 3Sum Closest

611. Valid Triangle Number

A similar O( n^2 ) solution to 3-Sum -solution-to-3-Sum)

For this problem, once we sort the input array nums, the key to solve the problem is that given nums[k], count the combination of i and j where nums[i] + nums[j] > nums[k] (so that they can form a triangle).

把3-Sum中if条件换一下，就可以应用在这个题中。

If nums[i] + nums[j] is larger than nums[k], we know that there will be j - i combination.

注意这里计算个数的时候没有+1，来具体看一下计算的过程：

1 2	i j k [3, 19, 22, 24, 35, 82, 84]

因为3 + 82 > 84并且所有3和82之间的数(不包括82)都是大于等于3的，所以有j-i种组合可以形成三角形，它们分别是:

628. Maximum Product of Three Numbers

1	res = max( (biggest1 * biggest2 * biggest3), (smallest1 * smallest2 * biggest1) )

4元组

18. 4Sum

Python 140ms beats 100%, and works for N-sum (N>=2))

数组-选择子集

不固定个数

固定个数

2元组

3元组

4元组

Comments: