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<n ){
sum += nums[right] ;
while(sum>=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<nums.length; i++){
res[i] *= left ;
left *= nums[i] ;
res[nums.length-i-1] *= right;
right *= nums[nums.length-1-i] ;
}
return res ;
}
}
这样写看起来更容易理解，效率也更高了。
class Solution {
public int[] productExceptSelf(int[] nums) {
//每个值得左侧累乘值乘以右侧累乘值
int [] res = new int [nums.length] ;
int left=1, right=1 ;
for(int i=0; i<nums.length; i++){
res[i] = left ;
left *= nums[i] ;
}
for(int i=nums.length-1; i>=0; i--){
res[i] *= right ;
right *= nums[i] ;
}
return res ;
}
}
3-连续数组
题目链接：题目链接戳这里！！！
思路：前缀和+哈希表，将数组0都变为1，就变成了求前缀和为0得连续数组得最大长度。
AC代码如下：
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer,Integer> map = new HashMap<>() ;
int n = nums.length ;
for(int i=0; i<n; i++){
if(nums[i]== 0){
nums[i] = -1 ;
}
}
int sum = 0, temp = 0 ;
for(int i=0; i<n; i++){
sum += nums[i] ;//前缀和
if(sum==0){//前缀和为0
temp = i+1;
}
if(map.containsKey(sum)){//前缀和为0
temp = Math.max(i-map.get(sum),temp) ;
}else{
map.put(sum, i) ;
}
}
return temp ;
}
}
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<Integer, Integer> map = new HashMap<>() ;
for(int i=0; i<n; i++){
sum += nums[i] ;
int temp = sum % k ;
if(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<n-1; i++){
sums[i+1] = sums[i] + nums[i+1] ;
}
int cnt = 0 ;
for(int i=0; i<n; i++){
if(sums[i]==k){
cnt ++ ;
}
for(int j=i+1; j<n; j++){
if(sums[j]-sums[i]==k){
cnt ++ ;
}
}
}
return cnt ;
}
}
还是用前缀和+哈希表，把时间复杂度降为O(n)
AC代码如下：
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length ;
Map<Integer, Integer> map = new HashMap<>() ;
int cnt = 0,sum = 0 ;
for(int i=0; i<n; i++){
sum += nums[i] ;
if(sum==k){
cnt ++ ;
}
if(map.containsKey(sum-k)){
cnt += map.get(sum-k) ;
}
map.put(sum, map.getOrDefault(sum, 0)+1) ;
}
return cnt ;
}
}
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(;right<A.length; right++){
if(A[right]==0){
zero++ ;
}
while(zero>K){
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(;right<A.length; right++){
if(A[right]==0){
zero++ ;
}
if(zero>K){
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<n; i++){ //从第2个开始求和等于0，则第一个是中心
sum += nums[i] ;
}
if(sum==0){
return 0 ;
}
int [] sums = new int [n] ;
sums[0] = nums[0] ;
for(int i=0; i<n-1; i++){ //求前缀和
sums[i+1] = sums[i] + nums[i+1] ;
}
for(int j=0; j<n; j++){ //右侧前缀和等于左侧则找到了
if(j+1<n && sums[j] == (sums[n-1]-sums[j+1])){
return j+1 ;
}
}
return -1 ;
}
}
8-和相同的二元子数组
题目链接：题目链接戳这里！！！
思路：前缀和+哈希表
每次记录前缀和，找到所有前缀和值为goal的。
AC代码如下：
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
//前缀和+hash表
int sum = 0, cnt = 0;
Map<Integer, Integer> map = new HashMap<>() ;
for(int i=0; i<nums.length; i++){
sum += nums[i] ;
if(sum==goal){
cnt ++ ;
}
if(map.containsKey(sum-goal)){
cnt += map.get(sum-goal) ;
}
map.put(sum, map.getOrDefault(sum,0)+1) ;
}
return cnt ;
}
}
意难平终将和解，万事终将如意，加油吧，少年。