Some topics about arrays

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];
        }
    }
    

Posted by prue_ on Sat, 07 May 2022 10:21:57 +0300