array_leetcode
秋水 Lv5
 2023-12-30 23:06:51  

处理和解决编程面试问题的最佳技巧

    1. 把问题画出来，形象化

      有没有想过为什么编码面试传统上是在白板上完成的，而解释编码问题答案的视频往往使用图表？白板使绘制图表变得容易，有助于解决问题！编码的很大一部分是理解程序的内部状态如何变化，而图表是表示内部数据结构状态的超级有用的工具。如果您很难理解解决方案是如何获得的，请提出问题的可视化表示，并在必要时提出每个步骤的内部状态。

      如果输入涉及树、图形、矩阵、链表，则此技术特别有用。

    2. 想想你会如何手工解决这个问题

      手动解决问题就是在不编写任何代码的情况下解决问题，就像非程序员一样。大多数时候，当您试图理解给您的示例时，这已经自然而然地发生了。

      有些人没有意识到的是，有时有效的解决方案只是手动方法的代码版本。如果你能围绕适用于每个示例的方法提出一套具体的规则，你就可以为它编写代码。虽然这样做可能无法达到最有效的解决方案，但这是一个会给您带来一些信任的开始。

    3. 想出更多的例子

      想出更多的例子是你可以做的有用的事情，无论你是否被困住了。它可以帮助您加强对问题的理解，防止您过早地进入编码，帮助您识别可以推广到任何输入的模式，这就是解决方案！最后，在验证解决方案时，可以将多个示例用作最后的测试用例。

    4. 将问题分解为更小的独立部分

      如果问题很大，则从高级函数开始，然后将其分解为更小的构成函数，分别求解每个函数。这可以防止您被一次做所有事情的细节所淹没，并保持您的思维结构化。

      这样做也让面试官清楚地知道你有一种方法，即使你没有设法完成所有较小函数的编码。

    5. 在问题中应用常见的数据结构和算法

数组问题

面试数组注意的问题

  1. 阐明数组中是否存在重复值。重复值的存在会影响答案吗？它使问题变得更简单还是更难？

    answer

    分情况讨论

    • 问题变得简单的情况：
      • 比如查找，如果查找特定的值，那么重复就会变得更快，
    • 问题变得复杂：
      • 唯一行检查，检查是否是数组中的唯一值，那么重复值就增加了问题的复杂度
      • 排序问题：在排序算法中，重复值可能需要特殊的处理，特别是需要稳定的排序

  2. 使用索引遍历数组时，请注意不要越界

  3. 请注意在代码中对数组进行切片或连接。通过切片和连接需要O(n)时间，在可能的情况下，使用开始和结束索引来划分子数组/范围

极端情况

  1. 空序列
  2. 具有1个或2个元素的序列
  3. 具有重复元素的序列
  4. 序列中的重复值

HashSet

  1. 无需集合
  2. 唯一性，不允许有重复的原色
  3. 给予哈希表
  4. 空值，允许存储一个null元素
  5. 非线程安全

解决数组问题常用的方法

滑动窗口

  1. 题目 给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

    示例 1:

    1
    2
    3
    输入: s = "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

    示例 2:

    1
    2
    3
    输入: s = "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

    示例 3:

    1
    2
    3
    4
    输入: s = "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
         请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

    示例 4:

    1
    2
    输入: s = ""
    输出: 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        //哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n =s.length();
        //右指针，初值为-1，相当于在我们字符串左边界的左侧，还没有开始移动
        int rk = -1, ans=0;
        for(int i = 0; i < n; i++){
           if(i !=0 ){
               //左指针向右移动一格，移除一个字符
               occ.remove(s.charAt(i-1));
           } 
            while (rk + 1 < n && !occ.contains(s.charAt(rk+1))){
                //不断的移动右指针
                occ.add(s.charAt(rk+1));
                rk++;
            }
            // 第i到rk个字符是一个极长的无重复字符字串
            ans = Math.max(ans, rk-i+1); 
        }
        return ans;
    }
}

  1. 给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    示例 1：

    1
    2
    3
    输入：target = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。

    示例 2：

    1
    2
    输入：target = 4, nums = [1,4,4]
    输出：1

    示例 3：

    1
    2
    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    输出：0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

  1. 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

    注意：

    • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

    示例 1：

    1
    2
    3
    输入：s = "ADOBECODEBANC", t = "ABC"
    输出："BANC"
    解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

    示例 2：

    1
    2
    3
    输入：s = "a", t = "a"
    输出："a"
    解释：整个字符串 s 是最小覆盖子串。

    示例 3:

    1
    2
    3
    4
    输入: s = "a", t = "aa"
    输出: ""
    解释: t 中两个字符 'a' 均应包含在 s 的子串中，
    因此没有符合条件的子字符串，返回空字符串。

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class Example3 {

    // ori存储字符中t中每个字符出现的次数
    Map<Character, Integer> ori = new HashMap<Character , Integer>();

    // cnt存储s字串中的每个字符的位置
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public  String minWindow(String s , String t){
        // 遍历字符串t， 统计每个字符的出现次数
        for (int i = 0; i < t.length(); i++){
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0)+1);
        }

        //初始化左右指针和答案变量
        int l=0, r=-1;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();

        // 开始滑动窗口
        while (r < sLen){
            r++;
            // 当右指针指向的字符在t中时，将其计入cnt
            if (r < sLen && ori.containsKey(s.charAt(r))){
                cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r),0)+1);
            }
            //当当前字串符合条件是，尝试缩小左指针以找到最小字串
            while (check() && l <= r){
                //如果当前窗口的长度 小于之前找到的最小长度
                if (r - l + 1 <len){
                    len = r - l + 1;
                    ansL = l;
                    ansR = l+len;
                }
                // 缩小窗口的同时，更新cnt中对应字符的计数
                if (ori.containsKey(s.charAt(l))){
                    cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l),0)-1);
                }
                l++;
            }
        }
        // 如果找到了符合条件的子串，返回它；否则返回空字符串
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

    /**
     * 用于查询是否符合规则
     * @return boolean
     */
    public boolean check(){
        // 遍历ori映射中的每个迭代器
        Iterator<Map.Entry<Character, Integer>> iterator = ori.entrySet().iterator();
        // 遍历ori映射
        while (iterator.hasNext()){
            //获取下一个键值对
            Map.Entry<Character, Integer> entry = iterator.next();
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (cnt.getOrDefault(key,0) < value){
                return false;
            }
        }
        return true;
    }
}

双指针解题思路

(一般用于定义p0,p1)

example1

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

1
2
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

1
2
输入：nums = [2,0,1]
输出：[0,1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void sortColoers(int[] nums){
      int n = nums.length;
      int p0 = 0, p2 = n - 1;
      for (int i = 0 ; i <= p2; i++){
          while(i <= p2 && nums[i] == 2){
              int tmp = nums[i];
              nums[i] =  nums[p2];
              nums[p2] = tmp;
              --p2;
          }
          if (nums[i] == 0){
              int tmp = nums[i];
              nums[i] = nums[p0];
              nums[p0] = tmp;
              ++p0;
          }
      }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void sortColoers2(int[] nums){
        int n = nums.length;
        int p0=0, p1=1;
        for (int i = 0; i < n ; i++){
            if (nums[i] == 1){
                int tmp = nums[i];
                nums[i] = nums[p1];
                nums[p1] = tmp;
                ++p1;
            }else if (nums[i] == 0){
              int tmp = nums[i];
              nums[i] = nums[p0];
              nums[p0] = tmp;
              if (p0 < p1){
                  tmp = nums[i];
                  nums[i]  =nums[p1];
                  nums[p1] = tmp;
              }
              ++p0;
              ++p1;
            }
        }

    }

Example2

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

两种解法： 一种新开辟空间，一种在以前的基础上，不开辟空间

解1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1= 0, p2=0;
        int[] sorted = new int[m+n];
        int cur;
        while(p1 < m || p2 < n){
          //如果走到数组1的末尾
            if(p1 == m){
                cur = nums2[p2++];
            }else if (p2 == n){
              //如果走到数组2的末尾
                cur = nums1[p1++];
            }else if(nums1[p1] < nums2[p2]){
                cur = nums1[p1++];
            }else {
                cur = nums2[p2++];
            }
            //将选定的元素 cur 放入 sorted 数组中。由于 p1 和 p2 都是从0开始的，并且在选择元素后才自增，所以实际索引为 p1 + p2 - 1
            sorted[p1+p2 -1] = cur;
        }
        for(int i = 0 ; i !=m+n; i++){
            nums1[i] = sorted[i];
        }
    }
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  int p1=m-1, p2=n-1;
        int tail = m+n-1;
        int cur;
        while(p1 >=0 || p2>=0){
            if(p1 == -1){
                cur = nums2[p2--];
            }else if (p2 == -1){
                cur = nums1[p1--];
            }else if(nums1[p1] > nums2[p2]){
                cur = nums1[p1--];
            }else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
//他需要的非递减序列，所以其实怎么都够

example3 回文字串问题

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

1
2
3
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

1
2
3
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

解题代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countSubstrings(String s) {
       if(s == null || s.length() <=0 ){
           return 0;
       }
       int res = 0;
       int length= s.length();
       char[] chars =s.toCharArray();

       for(int i = 0 ; i < length; i++){
           res += countPalindrome(chars,i,i);
           res += countPalindrome(chars,i,i+1);
       }
        return res;
    }
    private int countPalindrome(char[] chars, int start, int end){
        int curRes = 0;
        int length = chars.length;
        while((start >= 0 ) && (end < length) && (chars[start--] == chars[end++])){
            curRes++;
        }
        return curRes;
    }
}

从后面往前逆回来走指针

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

解法：

从后往前算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        
        int len=temperatures.length;
        int[] ans = new int[len];
        for(int i = len -2 ; i>=0; i--){
            if(temperatures[i] < temperatures[i+1]){
              //如果后一天的温度比前一天的高，那你就直接等于1
                ans[i]=1;
            }else {
                int j = i+1;
                //定义j是i的下一天
                // ans[j]>0 说明后面还有更热的天 说明有比当前更热的天
                while(ans[j] > 0 && temperatures[i] >= temperatures[j]){//这里如果ans[j] =0 说明后面的每一天都不如今天的温度高
                    j+=ans[j];
                  //这里就是直接跳跃，假如你有比今天更热的天，那就直接跳跃到这一天
                }
                if(temperatures[i] < temperatures[j]){
                    ans[i]=j-i;
                  // ans的结果就是这两天的差
                  //如果 今天的温度 还要比之后的更高，那就是0
                }
            }
        }
     return ans; 
    }
}

单调栈解法

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
// method2 单调栈的方法
    int length = temperatures.length;
    int[] ans = new int[length];
    Deque<Integer> stack = new LinkedList<Integer>();
    for(int i=0; i< length; i++){
        int temperature = temperatures[i];
        while(!stack.isEmpty() && temperature > temperatures[stack.peek()]){
            int prevIndex =stack.pop();
            ans[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return ans;

单调栈的解题思路

  1. 单调栈，其中的元素是单调递增或者递减。
  2. 解题思路如何下
    1. 确定单调性：确定使用的是递增栈还是递减栈，如果你要找到每一个右则第一个更大的元素，应该使用递减栈（从栈底到栈顶以此减小）
    2. 处理元素，如果栈非空且栈顶元素小于当前元素，出栈栈顶元素，并记录当前元素是栈顶元素右侧第一个更大的元素
    3. 遍历结束后，栈中剩余的元素没有右侧更大的元素，可以根据需求处理

排序问题

解题思路： 重写Comparator接口 Comparator接口可以用过Arrays.sort()来重新实现， 方法参数 ：void sort(T[] a, Comparator<? super T> c)

如何实现重写

通过匿名内部类。new Comparator(){

​ public int compare(object t1, object t2){

​ return t1.value - t2.value;

}

}

example1 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[][] merge(int[][] intervals) {
        int len = intervals.length;
        if(len < 2){
            return intervals;
        }
        //按照起点排序
        Arrays.sort(intervals, new Comparator<int[]> (){
            public int compare(int[] interval1, int[] interval2){
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merge = new ArrayList<int[]>();
        for(int i = 0; i < intervals.length; i++){
            int L = intervals[i][0] , R = intervals[i][1];
            if(merge.size() == 0 || merge.get(merge.size() -1)[1] < L){
                merge.add(new int[]{L,R});
            }else{
                merge.get(merge.size() -1)[1] = Math.max(merge.get(merge.size() -1)[1], R);
            }
        }
         return merge.toArray(new int[merge.size()][]);
    }
   
}

预计算

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(*n*) 时间复杂度内完成此题。

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

解法1双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] productExceptSelf(int[] nums) {
        //维护两个变量，beforeSum表示前缀和，aferSum表示后缀和
        int n = nums.length;
        int[] ans=new int[n];
        Arrays.fill(ans,1);
        int brforeSum = 1;
        int afterSum = 1;
        for(int i = 0, j = n - 1; i < n; i++,j--){
            ans[i]*=brforeSum;
            ans[j]*=afterSum;
            brforeSum*=nums[i];
            afterSum*=nums[j];
        }
        return ans;
    }
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] productExceptSelf(int[] nums) {
       int length = nums.length;
       //L和R分别表示左右两侧的乘积列表
       int[] L = new int[length];
       int[] R = new int[length];

       int[] answer = new int[length];

       //L[i]为索引i左侧的所有元素的乘积
       //对于索引为0的元素，因为左侧没有元素，所以L[0] = 1
       L[0] =1;
       for(int i = 1; i < length; i++){
           L[i] = nums[i-1] * L[i-1];
       } 

       //R[i]为索引i右侧所有元素的乘积
       //对于索引为length-1的元素，因为右侧没有元素，所以R[lenght-1]=1
       R[length-1] = 1;
       for(int i = length-2; i >= 0; i--){
           R[i] = nums[i+1]*R[i+1];
       }
       /**对于索引i，除nums[i]之外其余各元素的乘积就是左侧所有
       元素的乘积乘以右侧所有元素的乘积
        */
        for(int i = 0; i < length; i++){
            answer[i] = L[i] * R[i];
        }
    return answer;
    }
}

解法2节省空间办法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] productExceptSelf(int[] nums) {
       int length = nums.length;
      int[] answer = new int[length];
      answer[0]=1;
      for(int i = 1; i < length;i++){
          answer[i] = answer[i-1]*nums[i-1];
      }
      int tmp=1;
      for(int j = length-1; j>=0; j--){
           
          answer[j]= answer[j]*tmp;
           tmp*=nums[j];
      }
    return answer;
    }
}

subject2

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解法1 暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int length = nums.length;
        int ans=Integer.MAX_VALUE;
        int sum=0;
        if(n == 0){
            return 0;
        }
        for(int i = 0 ; i < length; i++){
            sum=0;
            for(int j = i; j < length; j++){
                sum+=nums[j];
                if(sum > target){
                    break;
                }else if(target == sum){
                    ans = Math.min(ans,j-i+1);  
                }
            }
        }
         return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

解法2 滑动窗口 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int length = nums.length;
        int ans=Integer.MAX_VALUE;
        int left = 0;//滑动窗口左边界
        int sum = 0;
        for(int i = 0; i < length ; i++){
          sum += nums[i];
          while(sum >= target){
              ans = Math.min(ans,i-left+1);
              sum -= nums[left];
              left++;
          }
        }
        return ans == Integer.MAX_VALUE?0:ans;
    }
}

索引作为哈希

缺失的正整数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
2
3
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

1
2
3
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

1
2
3
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

解答1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for(int num : nums){
            numSet.add(num);
        }
        int missingPositve = 1;
        while(numSet.contains(missingPositve)){
            missingPositve++;
        }
        return missingPositve;
    }
}

解答2 空间复杂度为o(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}


  • Post title：array_leetcode
  • Post author：秋水
  • Create time：2023-12-30 23:06:51
  • Post link：tai769.github.io2023/12/30/array_leetcode/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.