leetcode之前缀和刷题总结1

leetcode之前缀和刷题总结1

1-长度最小的子数组
题目链接：题目链接戳这里！！！

思路：前缀和+二分查找
求出数组的前缀和，在前缀和中二分查找并更新最小的子数组

AC代码如下：

class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length ; int [] sums = new int [n+1] ; int min = Integer.MAX_VALUE ; for(int i=1; i<=n; i++){ //前缀和 sums[i] = sums[i-1]+nums[i-1]; } for(int i=1; i<=n; i++){//二分查找 int s = target + sums[i-1] ; int bound = Arrays.binarySearch(sums,s) ; if(bound<0){ bound = -bound - 1 ; } if(bound<=nums.length){ min = Math.min(min,bound-(i-1)) ; } } return min==Integer.MAX_VALUE ? 0 : min ; }}

方法2：双指针法

class Solution { public int minSubArrayLen(int target, int[] nums) { int n = nums.length ; int min = Integer.MAX_VALUE ; int sum = 0 ; int left=0, right = 0 ; while(right=target){ min = Math.min(min, right-left+1) ; sum -= nums[left] ; left++ ; } right++ ; } return Integer.MAX_VALUE==min ? 0 : min ; }}

2-除自身以外得数组得乘积
题目链接：题目链接戳这里！！！

AC代码如下：

思路：就是求出每个值得左侧累乘乘以右侧累乘。

class Solution { public int[] productExceptSelf(int[] nums) { //每个值得左侧累乘值乘以右侧累乘值 int [] res = new int [nums.length] ; int left=1, right=1 ; Arrays.fill(res,1) ; for(int i=0; i

这样写看起来更容易理解，效率也更高了。

class Solution { public int[] productExceptSelf(int[] nums) { //每个值得左侧累乘值乘以右侧累乘值 int [] res = new int [nums.length] ; int left=1, right=1 ; for(int i=0; i=0; i--){ res[i] *= right ; right *= nums[i] ; } return res ; }}

3-连续数组
题目链接：题目链接戳这里！！！

思路：前缀和+哈希表，将数组0都变为1，就变成了求前缀和为0得连续数组得最大长度。

AC代码如下：

class Solution { public int findMaxLength(int[] nums) { Map map = new HashMap<>() ; int n = nums.length ; for(int i=0; i

4-连续得子数组和
题目链接：题目链接戳这里！！！

思路：前缀和+哈希表
如果前缀和对k取余为0，且数组长度为2以上，则为真
如果前缀和相等，且数据长度为2以上，则为真，
否则为假。

AC代码如下：

class Solution { public boolean checkSubarraySum(int[] nums, int k) { //前缀和+哈希表 int n = nums.length ; if(n<2){ return false ; } int sum = 0 ; Map map = new HashMap<>() ; for(int i=0; i=1 && temp==0){//前缀和对k取余等于0 return true ; } if(map.containsKey(temp)){ //前缀和对k取余相等且下标大于等于2则符合 int preIndex = map.get(temp) ; if(i-preIndex>=2){ return true ; } }else{ map.put(temp, i) ; } } return false ; }}

5-和为K得子数组
题目链接：题目链接戳这里！！！

思路1：直接用前缀和统计，这样得话需要双重循环，时间复杂度较高，不过这题的测试用例O(n^2)的复杂度也可以通过

AC代码如下：

class Solution { public int subarraySum(int[] nums, int k) { int n = nums.length ; int [] sums = new int [n] ; sums[0] = nums[0] ; for(int i=0; i

还是用前缀和+哈希表，把时间复杂度降为O(n)
AC代码如下：

class Solution { public int subarraySum(int[] nums, int k) { int n = nums.length ; Map map = new HashMap<>() ; int cnt = 0,sum = 0 ; for(int i=0; i

6-最大连续1的个数III
题目链接：

思路：双指针，也叫滑动窗口。

class Solution { public int longestOnes(int[] A, int K) { int left=0, right=0;//窗口左右侧 int max = 0 ;//最大窗口 int zero=0 ;//窗口中0的个数 for(;rightK){ if(A[left++]==0){ zero-- ; } } max = Math.max(max, right-left+1) ; } return max ; }}

不需要while循环的滑动窗口

class Solution { public int longestOnes(int[] A, int K) { int left=0, right=0;//窗口左右侧 int zero=0 ;//窗口中0的个数 for(;rightK){ zero -= (1 - A[left++]) ; } } return right - left ; }}

7-寻找数组的中心下标
题目链接：题目链接戳这里！！！

思路：判断左右端的前缀和是否相等即可。

AC代码如下：

class Solution { public int pivotIndex(int[] nums) { int n = nums.length ; int sum = 0 ; for(int i=1; i

8-和相同的二元子数组
题目链接：题目链接戳这里！！！

思路：前缀和+哈希表
每次记录前缀和，找到所有前缀和值为goal的。

AC代码如下：

class Solution { public int numSubarraysWithSum(int[] nums, int goal) { //前缀和+hash表 int sum = 0, cnt = 0; Map map = new HashMap<>() ; for(int i=0; i

意难平终将和解，万事终将如意，加油吧，少年。