阿翰剑指offer专项突破Day03数组数组

68 阅读 0 评论 45 点赞

我是靠谱客的博主大方铃铛，最近开发中收集的这篇文章主要介绍阿翰剑指offer专项突破Day03数组数组，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

数组

1 数组中和为 0 的三个数

2 和大于等于 target 的最短子数组

滑动窗口法

3 乘积小于 K 的子数组

滑动窗口法

数组

1 数组中和为 0 的三个数

剑指 Offer II 007. 数组中和为 0 的三个数https://leetcode-cn.com/problems/1fGaJU/

此题为「排序数组中两个数字之和」的加强版。

数组有有序的时候，固定一个i，在排序数组里找和为-i的数字即可，通过前一题，有了双指针寻找和为定值的O(n)方法，因此复杂度为O(n^2)。由于题目给的不是排序的数组，排序算法的时间复杂度一般为O(nlogn)，最后总时间复杂度为O(nlogn)+O(n^2)，最后仍是O(n^2)。

注意：去重三元组

即找到一个符合要求的三元组后，既然是排序数组，可以通过一个temp值临时存储第一、二个值，两次循环判断直到不同再break，以过滤重复的数字。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length >= 3){
            Arrays.sort(nums);
            int i = 0;
            while(i < nums.length - 2){
                twoSum(nums, i, result);
                int temp = nums[i];
                while(i < nums.length && nums[i] == temp)
                    ++i;
            }
        }
        return result;
    }
    public void twoSum(int[] nums, int i, List<List<Integer>> result){
        int j = i + 1;
        int k = nums.length - 1;
        while(j < k){
            if(nums[i] + nums[j] + nums[k] == 0){
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));
//                去重
                int temp = nums[j];
                while(nums[j] == temp && j < k){
                    ++j;
                }
            } else if (nums[i] + nums[j] + nums[k] < 0){
                ++j;
            } else{
                --k;
            }
        }
    }
}

2 和大于等于 target 的最短子数组

剑指 Offer II 008. 和大于等于 target 的最短子数组https://leetcode-cn.com/problems/2VG8Kg/

滑动窗口法

让两个指针先指向第一个数字，right向右移动，求和sum，直到sum大于目标数字target，说明此时满足要求了，可以求minLength，再对sum减去nums[left++]，直到sum小于目标数字target。

package zxtp.Day01;

/**
 * @author ahan
 * @create_time 2022-01-29-5:11 下午
 */
public class _008 {
    public static void main(String[] args) {
        System.out.println(new _008().minSubArrayLen(7, new int[]{2,3,1,2,4,3}));
    }
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (left <= right && sum >= target){
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left++];
            }   
        }
        return minLength == Integer.MAX_VALUE ? 0 :minLength;
    }
}

本方法中left和right俩指针只增加不减少，right从0增加到到n-1，left最多增加到n-1，时间复杂度为O(n)。

3 乘积小于 K 的子数组

滑动窗口法

剑指 Offer II 009. 乘积小于 K 的子数组https://leetcode-cn.com/problems/ZVAVXX/

和前一题思路一致~

package zxtp.Day01;

/**
 * @author ahan
 * @create_time 2022-01-29-5:55 下午
 */
public class _009 {
    public static void main(String[] args) {
        System.out.println(new _009().numSubarrayProductLessThanK(new int[]{10, 5, 2, 6}, 100));
    }
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int product = 1;
        int left = 0;
        int count = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while(left <= right && product >= k)
                product /= nums[left++];
            count += right >= left ? right - left + 1 : 0;
        }
        return count;
    }
}