1. Three numbers with zero in the array
-
describe
Given an array num containing n integers, judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with a sum of 0 and no duplicates.
-
solution
In terms of violence, we should use triple loops for arrays and judge them one by one. The triple loop can be simplified to a single loop and double pointers. For each value, use double pointers to determine whether there are two values after it and its sum is equal to zero. You can sort first. After sorting, values greater than 0 can be discarded directly. Pay attention to the same elements, such as (- 1, 0, 1, 1, 1). If the title requires non repeated combinations, this situation must be excluded.
-
Source code
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); int len = nums.length; for(int i=0; i<len; i++){ //If it is greater than 0, the value will not exist if(nums[i] > 0) break; //The purpose here is to prevent the occurrence of duplicate values. Instead of judging them, it is directly to the next one if(i>0 && nums[i]==nums[i-1]) continue; int start = i+1; int end = len-1; while(start < end){ int total = nums[i]+nums[start]+nums[end]; if(total == 0) { res.add(Arrays.asList(nums[i],nums[start],nums[end])); //You can't break directly here; while(start<end && nums[start]==nums[start+1]) start++; start++; } else if(total < 0) start++; else if(total > 0) end--; } } return res; } }
2. And the shortest subarray greater than or equal to target
-
describe
Given an array containing n positive integers and a positive integer target. Find out the continuous sub array [numsl, numsl + 1,..., numsr-1, numsr] with the smallest length satisfying its sum ≥ target in the array, and return its length. If there is no eligible subarray, 0 is returned.
-
solution
The essence of finding the data that meets the conditions in the array is to traverse the array. How to traverse the data that meets the conditions is more efficient. Different topics have different skills. For this problem, find the front boundary for each back boundary. We can first make the front boundary immobile and move the rear boundary. After the condition of > is met, it shows that there is a start boundary for this end boundary. Since the minimum value is required, sum - = num [start], start + +.
-
Source code
class Solution { public int minSubArrayLen(int target, int[] nums) { int start = 0; int end = 0; int res = Integer.MAX_VALUE; int len = nums.length; int sum = 0; while(end<len){ //For each back boundary, find the appropriate front boundary to ensure the integrity of data traversal sum += nums[end]; while(sum>=target){ sum -= nums[start]; res = Math.min(res,end-start+1); start++; } end++; } return res==Integer.MAX_VALUE ? 0 : res; } }
3. Subarray with product less than K
-
describe
Given a positive integer array nums and integer k, please find out the number of consecutive sub arrays whose product is less than K in the array.
-
solution
This is also a problem of finding intervals. It still needs to be traversed. First, find the interval satisfying the condition according to the method of the above question, that is, the while loop of the inner layer, or find the start boundary for the end boundary. After finding it, it is reasonable to say that all combinations in this interval are only satisfied, and res should be + = (j-i+1)!, However, there must be repeated parts between intervals, which must be less than this value. (j-i+1) is only the number of elements in the interval I don't quite understand here
-
Source code
class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { int res = 0; int start = 0; int end = 0; int add = 1; int len = nums.length; while(end < len){ add *= nums[end]; while(start<=end && add>=k){ add /= nums[start]; start++; } res += end-start+1; end++; } return res; } }
4. Subarray with and K
-
describe
Given an array of integers and an integer k, please find the number of consecutive subarrays with K in the array.
-
solution
For many continuous interval problems, prefix and can be used, and the above problems can also be used. The combination of prefix and map is sometimes very effective. The sum of subarrays is k, which is prefix[j]-prefix[i] == k. This solution uses map to quickly find the number of occurrences of prefix[i]
-
Source code
class Solution { public int subarraySum(int[] nums, int k) { int len = nums.length; int res = 0; int [] prefix = new int[len+1]; Map<Integer,Integer> map = new HashMap<>(); map.put(0,1); for(int i=1; i<=len; i++){ //Calculate the prefix sum of the point, and judge whether prefix[i]-k is stored in the map, if any prefix[i] = prefix[i-1]+nums[i-1]; if(map.containsKey(prefix[i]-k)) res+=map.get(prefix[i]-k); //There may be 0, so that the prefix and of the same value exist map.put(prefix[i],map.getOrDefault(prefix[i],0)+1); } return res; } }
5. The longest continuous subarray of the same number of 0 and 1
-
describe
Given a binary array nums, find the longest continuous sub array containing the same number of 0 and 1, and return the length of the sub array.
-
solution
Whether it is an interval or a combination of prefix and map. But there is no rule to add the prefix of 0 and 1. Here are some tips. When 0 is encountered, the prefix and - 1 are given. When the prefix and corresponding to the two subscripts are the same, it means that the number of 0 and 1 in this interval is the same. It should be noted that when the value appears in the front, in order to ensure that the longest interval is obtained, do not add the value to the map.
-
Source code
class Solution { public int findMaxLength(int[] nums) { int len = nums.length; int[] preSum = new int[len+1]; Map<Integer,Integer> map = new HashMap<>(); map.put(0,0); int max = 0; for(int i=1; i<=len; i++){ preSum[i] = preSum[i-1] + (nums[i-1]==0 ? -1 : 1); if(map.containsKey(preSum[i])){ max = Math.max(max,i-map.get(preSum[i])); } //Add the subscript to the map before it appears. Make sure that the subscript stored in the map is where it appears for the first time else map.put(preSum[i],i); } return max; } }
6. The left and right array values are equal
-
describe
Give you an integer array nums, please calculate the central subscript of the array. The central subscript of the array is a subscript of the array. The sum of all elements on the left is equal to the sum of all elements on the right. If the central subscript is at the leftmost end of the array, the sum of the numbers on the left is regarded as 0 because there is no element to the left of the subscript. The same applies when the central subscript is at the rightmost end of the array. If the array has multiple central subscripts, the one closest to the left should be returned. Returns - 1 if the array does not have a central subscript.
-
solution
The left and right sides are still intervals, or you can use prefixes and. But here, according to the requirements of the topic, sum * 2 + num [i] = = total, calculate and judge.
-
Source code
class Solution { public int pivotIndex(int[] nums) { int total = Arrays.stream(nums).sum(); int sum = 0; for(int i=0; i<nums.length; i++){ if(2*sum + nums[i] == total){ return i; } //Cumulative prefix sum sum += nums[i]; } return -1; } }
7. Sum of two-dimensional submatrix
-
describe
Given a two-dimensional matrix, multiple requests of the following types:
Calculate the sum of the elements within its sub rectangle. The upper left corner of the sub matrix is (row1, col1) and the lower right corner is (row2, col2).
Implement NumMatrix class: NumMatrix(int[][] matrix) initializes the given integer matrix. Int sum region (int row1, int col1, int row2, int col2) returns the sum of the elements of the sub matrix in the upper left corner (row1, col1) and the lower right corner (row2, col2).
-
solution
On a topic of matrix, it should be noted that the prefix and prefix [i + 1] [J + 1] are added to the matrix[i][j] of the matrix. Therefore, when calculating sumRegion(int row1, int col1, int row2, int col2), use prefix [col2 + 1] [rol + 1]
-
Source code
class NumMatrix { private int[][] preSum; public NumMatrix(int[][] matrix) { int m = matrix.length; if(m > 0 ){ this.preSum = new int[m+1][matrix[0].length+1]; for(int i=0; i<m; i++){ for(int j=0; j<matrix[0].length; j++){ preSum[i+1][j+1] = preSum[i][j+1]+preSum[i+1][j]-preSum[i][j]+matrix[i][j]; } } } } public int sumRegion(int row1, int col1, int row2, int col2) { return preSum[row2+1][col2+1] + preSum[row1][col1] - preSum[row1][col2+1]-preSum[row2+1][col1]; } }