1013.将数组分成和相等的三个部分

✒解题思路：

  1. 当整个数组的和不是3的倍数时，无法等分成三组，返回false
  2. 遍历数组求和，当部分和等于整个数组和的1/3时做标记，并将部分和置为零，当标记等于2说明能够分组
  3. 或者数组从前后分别求部分和，两个部分和等于整个数组和的1/3，说明能够分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int sum = 0;
		int recordSum = 0,num=0;
		for (int i = 0; i < A.length; i++) {
			sum+=A[i];
		}
		if(sum%3!=0){
			return false;
		}
		for (int i = 0; i < A.length-1; i++) {
			recordSum+=A[i];
			if(recordSum==(sum/3)){
				num++;
				recordSum=0;
				if(num==2){
					return true;
				}
			}
		}
		return false;
    }
}

1025.除数问题

✒解题思路：

  1. 当N为偶数时，Alice先手，只要减去1，Bob就会得到一个奇数，只能减去奇数，Alice得到偶数，最终当N=2时结束，Alice获胜
  2. 当N为奇数时，Alice先手，Bob会得到一个偶数，只要减去1，Alice就会得到奇数，最终当N=2时，Bob获胜
1
2
3
4
5
6
7
8
class Solution {
    public boolean divisorGame(int N) {
        if(N%2==0){
            return true;
        }
        return false;
    }
}

303.区域和检索-数组不可变

✒解题思路（官方）：

  1. 解法一，直接暴力
  2. 解法二，使用数组记录从0开始到i的部分和，获取i到j的部分和就可以sum[j+1]-sum[i]
1
2
3
4
5
6
7
8
9
10
11
12
class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length+1];
        for(int i=0;i<nums.length;i++){
            sum[i+1] = sum[i] + nums[i];
        }
    }
    public int sumRange(int i, int j) {
        return sum[j+1]-sum[i];
    }
}

42.连续子数组的最大和（Kadane’s Algorithm）

✒解题思路：

  1. 从头开始遍历数组，用sum保存部分和，max存储最大和，当sum小于nums[i]的值，舍弃sum，令sum=nums[i]，从当前开始遍历，比较max与sum的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxSubArray(int[] nums) {
		int sum = nums[0];
		int max = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if (sum + nums[i] < nums[i]) {
				sum = nums[i];
			} else {
				sum += nums[i];
			}
            if (sum > max) {
				max = sum;
			}
		}
		return max;
    }
}