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
意难平终将和解，万事终将如意，加油吧，少年。
