sum求和类题目

今天看到这道题目：http://www.cnblogs.com/charlesblc/p/5930311.html

题目地址：https://leetcode.com/problems/split-array-largest-sum/

很好，也很难。开拓了思路，用二分法来查找结果备选，然后直接划分原集合，来反过来是否是合理的解。是或者不是的话，继续向相应的方向进行二分。

	#	Title	Editorial	Acceptance	Difficulty	Frequency
。	454	4Sum II		43.3%	Medium
。	437	Path Sum III		38.7%	Easy
。	416	Partition Equal Subset Sum		37.5%	Medium
。	410	Split Array Largest Sum		32.2%	Hard
。	404	Sum of Left Leaves		45.7%	Easy
。	377	Combination Sum IV		41.6%	Medium
。	373	Find K Pairs with Smallest Sums		29.8%	Medium
。	371	Sum of Two Integers		51.4%	Easy
。	364	Nested List Weight Sum II		50.4%	Medium
。	363	Max Sum of Rectangle No Larger Than K		32.1%	Hard
。	339	Nested List Weight Sum		59.8%	Easy
。	327	Count of Range Sum		28.9%	Hard
。	325	Maximum Size Subarray Sum Equals k		41.6%	Medium
。	308	Range Sum Query 2D - Mutable		19.8%	Hard
。	307	Range Sum Query - Mutable		18.4%	Medium
。	304	Range Sum Query 2D - Immutable		22.7%	Medium
。	303	Range Sum Query - Immutable		26.2%	Easy
。	259	3Sum Smaller		40.6%	Medium
。	228	Summary Ranges		28.1%	Medium
。	216	Combination Sum III		41.9%	Medium
。	209	Minimum Size Subarray Sum		28.6%	Medium
。	170	Two Sum III - Data structure design		22.7%	Easy
。	167	Two Sum II - Input array is sorted		48.2%	Medium
。	129	Sum Root to Leaf Numbers		35.2%	Medium
。	124	Binary Tree Maximum Path Sum		25.0%	Hard
。	113	Path Sum II		31.4%	Medium
。	112	Path Sum		32.9%	Easy
。	64	Minimum Path Sum		37.2%	Medium
。	40	Combination Sum II		31.3%	Medium
。	39	Combination Sum		35.7%	Medium
。	18	4Sum		25.7%	Medium
。	16	3Sum Closest		30.5%	Medium
。	15	3Sum		20.9%	Medium
。	1	Two Sum		29.9%	Easy

先看的 

363

Max Sum of Rectangle No Larger Than K

32.1%

Hard

很难。看解法的时候，还看到一个很好的解法分析的页面：Link，能够处理 连续子数组求最大和 问题。

这个页面很好，层层递进，从最原始的O(n^3)的暴力查找，到记录sum(i)到i为止的和，然后sum(j)-sum(i) 得到sum(i...j)的方式，提升到O(n^2)；然后，通过分治法，一分为二的左右查找，然后中间从两边扩展再求和，将复杂度进一步有划到O(nlgn)。最后，解决DP的思想，直接采用max(j)= max(i) + sum(i...j)的方式，但是优化的是，max(i)如果是负数，就不用记录，用0就行了，所以其实可以O(n)的复杂度，直接进行求和，遇到和为负数就舍弃就可以了，复杂度为O(n)，已经最优化。（Kadane算法）

注意一个引申的是，找出和最大的矩阵。

我的方法是，先纵向处理，用sum(i)记录同一列中从最上方到i行的和，然后用sum(j)-sum(i)就能够求出这一列中的sum(i...j)，复杂度O(n)，

然后对于横向，对于每一个行的组合,用sum(i...j)作为基本元素，采用上面的Kadane算法来处理，复杂度一共 O(n*n*m)，所以取较小的一个维度为n.

而上面原题是对于sum有限制的，不大于某个数（比如k）的最大和。

参考解法里面的带的文章，可以得出，求出sum(i)后放入一个set，每次对于sum(j)，用一个upper_bound获得不小于sum(j)-k的sum(i)，这样sum(j)-sum(i)就小于k，并且是当前最大的了。

upper_bound是取得右侧范围，复杂度是O(lgn)，所以对于一维数组，复杂度是 O(nlgn)，而对于矩阵，复杂度是：

O[min(m,n)^2 * max(m,n) * log(max(m,n))], space O(max(m, n)).

特别注意的是，对于上面的space O(max(m, n)) 指的是对于用一列的结果（假设矩阵是扁的）不需要保存每一个sum(j), sum(i)，只需要循环的时候，直接得出同一列里面sum(i...j)就可以了，而对于横向，行的结果（每一行都很长），是需要算出每一个sum(a), 并且把结果保存到set里面的。

 

另外注意，stl里面set的底层实现是红黑树。另，map的底层实现也是红黑树。vector是动态数组实现。

另，用Java的TreeSet的ceiling可以模拟upper_bound（获得更大范围里面最小的数），floor可以模拟 lower_bound（获得更小范围内最大的数）。

好了，看这道题目：

327

Count of Range Sum

28.9%

Hard

我觉得是不是可以参考之前的放在set里面，然后用upper_bound或者lower_bound来处理。但是要注意的是，要用multiset，因为可能会有重复的元素。

解法中，也提到，可以用divide-and-conque方法，复杂度比naive方法，有所优化。

另外解法里提到的  https://discuss.leetcode.com/topic/33738/share-my-solution 里面关于 MergeSort模拟的方法，的确是正确的，虽然稍稍有点费解。仔细看了一下，还是能够理解的。

利用MergeSort还能处理个子排序的问题，就是一个人后面有几个人比自己高吧。有很多变通。

这道题目：

308

Range Sum Query 2D - Mutable

19.8%

Hard

在locked文件里面，有解法。

注意题目中有一句 "calls to update and sumRegion function is distributed evenly"

在update和sumRegion调用频率不同的情况下，可以有不同的对策。而对于调用频率相似的情况，那么解法中也给了折衷的方案。

当然，还有线段树的方法，但是面试中，一般不会涉及这一块。

124

Binary Tree Maximum Path Sum

25.0%

Hard

解法里面有。基本就是两课子树的递归，然后分别给出带root和不带root的，然后再用带root的跟本身的root做一下结合和比较处理。

18

4Sum

25.7%

Medium

解法非常好。我也想到了一定的思路。基本的基础是排序后两边向中间收敛。但是4sum多了对更多的两个元素的处理，以及一些去重的处理。

很好！

16

3Sum Closest

30.5%

Medium

开始我想到的是，先两端向中间收敛，然后找备选的第三个，但是发现实现有问题。所以更好的方法是，先选定一个，然后两端向中间收敛，通过与目标的比较，来确定是向上还是向下收敛。这种解法更好！

15

3Sum

20.9%

Medium

标准的固定一个，两边向中间收敛的解法。

39

Combination Sum

35.7%

Medium

标准的递归解法。先取一个元素，然后多次迭加之后，看剩余的数字，是否还有其他的结果。可以用DP.

40

Combination Sum II

31.3%

Medium

跟上面那个解法类似，就是每次去掉一个元素，同时这样也是可以用DP的。

216

Combination Sum III

41.9%

Medium

比上面那个简单一些，也是遍历。

377

Combination Sum IV

41.6%

Medium

这个跟Combination Sum 1 很相似，但是这个对于不同排序的结果算作多个。所以每次不用从下一个位置开始遍历，直接所有待选元素，是不是target减数字就可以了。

64

Minimum Path Sum

37.2%

Medium

这道题目，可以看每一个点，到这个位置的最小代价。 

1

Two Sum

29.9%

Easy

基本题。

112

Path Sum

32.9%

Easy

基本题，每次去掉root，然后递归。

113

Path Sum II

31.4%

Medium

跟上面那道题目一样的。

437

Path Sum III

38.7%

Easy

其实就是用了个递归做的。还是应该多考虑DP的。

454

4Sum II

43.3%

Medium

好！开始我想到的是先固定两个，然后另外两个，从两端向中间收敛。但是会有不少重复的情况。而我实际做的是，两两相加，通过Map或者HashMap来进行匹配，这样的话，其实是更加快的，而且应该重复的情况不多。

129

Sum Root to Leaf Numbers

35.2%

Medium

用的DFS深度遍历，用一个curVal记录当前的值。

209

Minimum Size Subarray Sum

28.6%

Medium

题目还是蛮好的。设置两个游标，一前一后。

259

3Sum Smaller

40.6%

Medium

下面代码是最终的解法，注意其中有两点：1是ret+的是end和front的距离，2是用了java的容器来实现引用传递。

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null)
            throw new IllegalArgumentException("nums is null");
        List<Integer> ret = new ArrayList<Integer> ();
        ret.add(0);
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            twoSumSmaller(nums, i + 1, target - nums[i], ret);
        }
        return ret.get(0);
    }
    
    private void twoSumSmaller(int[] nums, int i, int target, List<Integer> ret) {
        int front = i;
        int end = nums.length - 1;
        while (front < end) {
            if (nums[front] + nums[end] < target) {
                ret.set(0, ret.get(0) + end - front);
                front++;
            } else{
                end--;
            }
        }
    }
}

307

Range Sum Query - Mutable

18.4%

Medium

这个要用Binary-Index-Tree。挺难的！

后继：可以理解为节点的父亲节点。是离它最近的，且编号末位连续0比它多的就是它的父亲,如e[2]是e[1]的后继；e[4]是e[2]的后继。

　　　　　　如e[4] = e[2]+e[3]+a[4] = a[1]+a[2]+a[3]+a[4] ，e[2]、e[3]的后继就是e[4]。

　　　　　　后继主要是用来计算e数组，将当前已经计算出的e[i]添加到他们后继中。

　　　　前驱：节点前驱的编号即为比自己小的，最近的，最末连续0比自己多的节点。如e[7]的前驱是e[6],e[6]的前驱是e[4]。

 　　　　　  前驱主要是在计算连续和时，避免重复添加元素。

　　　　　　如：Sum(7)=a[1]+...+a[7]=e[7]+e[6]+e[4]。(e[7]的前驱是e[6], e[6]的前驱是e[4])

计算前驱与后继：

　　　　　　lowbit(i) = ( (i-1) ^ i) & i ;  （应该是只有一位是1，就是原数字最后面的一个1）

　　　　　　节点e[i]的前驱为 e[ i - lowbit(i) ]；

　　　　　　节点e[i]的后继为 e[ i + lowbit(i) ]

325

Maximum Size Subarray Sum Equals k

41.6%

Medium

方法还是很好的，一开始我没有想到。Hash用的很溜。

注意Hash里面只需要存一份，因为只留下标最前面的就行了。

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int[] sums = new int[nums.length];
        for(int i=0; i<nums.length; i++) {
            if (i==0) sums[i] = nums[i];
            else sums[i] = sums[i-1] + nums[i];
        }
        int max = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++) {
            if (sums[i]==k) max=Math.max(max, i+1);
            else {
                Integer j=map.get(sums[i]-k);
                if (j!=null) max = Math.max(max, i-j);
            }
            if (!map.containsKey(sums[i])) map.put(sums[i], i);
        }
        return max;
    }
}

339

Nested List Weight Sum

59.8%

Easy

这道题目的解法其实很不错：

两种方法都很经典：

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        int res = 0;
        for (auto a : nestedList) {
            res += getSum(a, 1);
        }
        return res;
    }
    int getSum(NestedInteger ni, int level) {
        int res = 0;
        if (ni.isInteger()) return level * ni.getInteger();
        for (auto a : ni.getList()) {
            res += getSum(a, level + 1);
        }
        return res;
    }
};

第二种：

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return helper(nestedList, 1);
    }
    int helper(vector<NestedInteger>& nl, int depth) {
        int res = 0;
        for (auto a : nl) {
            res += a.isInteger() ? a.getInteger() * depth : helper(a.getList(), depth + 1);
        }
        return res;
    }
};

364

Nested List Weight Sum II

50.4%

Medium

跟上面一道题目很类似。但是权重是从下往上增加。所以更难了。

其实方法也很直接。先检查最大深度，然后计算。就行了。

371

Sum of Two Integers

51.4%

Easy

把位运算的巧妙运用到了极致。

注意：if you want to get a negative number, you can simply do ~x + 1

题目非常好，看迭代的做法不大看的懂。看下面递归的方式，就容易理解多了：

// Recursive
public int getSum(int a, int b) {
    return (b == 0) ? a : getSum(a ^ b, (a & b) << 1);
}

// Recursive
public int getSubtract(int a, int b) {
    return (b == 0) ? a : getSubtract(a ^ b, (~a & b) << 1);
}

然后就可以看迭代的解法了：

// Iterative
public int getSum(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;

    while (b != 0) {
        int carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    
    return a;
}

// Iterative
public int getSubtract(int a, int b) {
    while (b != 0) {
        int borrow = (~a) & b;
        a = a ^ b;
        b = borrow << 1;
    }
    
    return a;
}

373

Find K Pairs with Smallest Sums

29.8%

Medium

我记录的解法，是非常好的。先用一个数组记录下搭档的位置，然后遍历数组，和搭档的位置一起匹配进行处理。另外，其实还可以加一次剪枝的方案在里面。

404

Sum of Left Leaves

45.7%

Easy

注意是叶子，所以函数里面带了一个参数来处理。

416

Partition Equal Subset Sum

37.5%

Medium

我觉得这道题目，跟 Combination Sum 系列很像。

求的结果，就是一半的结果。但是这里面既不用求个数，也不用打印，只需要判断是否存在。所以方法用的是加HashSet，然后对于HashSet里面没有元素，都累加当前元素，得到新的和。