Array is one of the fundamental blocks in data structure. Since a string is just formed by an array of characters, they are both similar. Most interview questions fall into this category.

In this card, we will introduce array and string. After finishing this card, you should:

  1. Understand the differences between array and dynamic array;
  2. Be familiar with basic operations in the array and dynamic array;
  3. Understand multidimensional arrays and be able to use a two-dimensional array;
  4. Understand the concept of string and the different features string has;
  5. Be able to apply the two-pointer technique to practical problems.

Introduction to Array

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
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize
        int[] a0 = new int[5];
        int[] a1 = {1, 2, 3};
        // 2. Get Length
        System.out.println("The size of a1 is: " + a1.length);
        // 3. Access Element
        System.out.println("The first element is: " + a1[0]);
        // 4. Iterate all Elements
        System.out.print("[Version 1] The contents of a1 are:");
        for (int i = 0; i < a1.length; ++i) {
            System.out.print(" " + a1[i]);
        }
        System.out.println();
        System.out.print("[Version 2] The contents of a1 are:");
        for (int item: a1) { // for each!!!
            System.out.print(" " + item);
        }
        System.out.println();
        // 5. Modify Element
        a1[0] = 4;
        // 6. Sort
        Arrays.sort(a1); // Arrays.sort(a1)!!!
    }
}

Introduction to Dynamic Array

Most programming languages offer built-in dynamic array which is still a random access list data structure but with variable size. For example, ArrayList in JAVA.

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
public class Main {
    public static void main(String[] args) {
        // 1. initialize
        List<Integer> v0 = new ArrayList<>();
        List<Integer> v1;                           // v1 == null
        // 2. cast an array to a vector(arraylist)
        Integer[] a = {0, 1, 2, 3, 4}; // Use Integer!!!
        v1 = new ArrayList<>(Arrays.asList(a)); // Arrays.asList(a)!!!
        // 3. make a copy
        List<Integer> v2 = v1;                      // another reference to v1
        List<Integer> v3 = new ArrayList<>(v1);     // make an actual copy of v1
        // 3. get length
        System.out.println("The size of v1 is: " + v1.size());
        // 4. access element
        System.out.println("The first element in v1 is: " + v1.get(0));
        // 5. iterate the vector
        System.out.print("[Version 1] The contents of v1 are:");
        for (int i = 0; i < v1.size(); ++i) {
            System.out.print(" " + v1.get(i));
        }
        System.out.println();
        System.out.print("[Version 2] The contents of v1 are:");
        for (int item : v1) { // for each!!!
            System.out.print(" " + item);
        }
        System.out.println();
        // 6. modify element
        v2.set(0, 5);       // modify v2 will actually modify v1
        System.out.println("The first element in v1 is: " + v1.get(0));
        v3.set(0, -1);
        System.out.println("The first element in v1 is: " + v1.get(0));
        System.out.println("The first element in v3 is: " + v3.get(0));
        // 7. sort
        v1.sort(Comparator.naturalOrder()); // Method 1!!!
        Collections.sort(v1); // Method 2!!!
        System.out.println("The contents of v1 after sort are:");
        for (int item : v1) {
            System.out.print(" " + item);
        }
        System.out.println();
        // 8. add new element at the end of the vector
        v1.add(-1);
        v1.add(1, 6);
        System.out.print("The contents of v1 after add are:");
        for (int item : v1) {
            System.out.print(" " + item);
        }
        // 1 6 2 3 4 5 -1
        System.out.println();
        // 9. delete the last element
        v1.remove(v1.size() - 1);
        System.out.println("The contents of v1 after remove are:");
        for (int i = 0; i < v1.size(); i++) {
            System.out.print(" " + v1.get(i));
        }
        // 1 6 2 3 4 5

        Integer[] ia = {1, 2, 3, 4, 5};
        Integer[] ib = {1, 2, 3, 4, 5};

        List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(ia)); // construct a new list!!!
        List<Integer> list2 = Arrays.asList(ib); // just wrap!!!

        System.out.println("The contents of list1");
        for (int item : list1) {
            System.out.print(" " + item);
        }
        System.out.println();

        System.out.println("The contents of list2");
        for (int item : list2) {
            System.out.print(" " + item);
        }
        System.out.println();

        ia[0] = 0;
        ib[0] = 0;

        System.out.println("The contents of list1 after modified");
        for (int item : list1) {
            System.out.print(" " + item);
        }
        // 1 2 3 4 5
        System.out.println();

        System.out.println("The contents of list2 after modified");
        for (int item : list2) {
            System.out.print(" " + item);
        }
        // 0 2 3 4 5
    }
}

Question - Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//    思路：
//            1. 如果末位小于 9 则直接加 1 返回；
//            2. 如果是 9 则置 0 后循环；
//            3. 如果都是 9 则手动建一个新数组，最前面置 1。
class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length - 1; i >= 0; i--){
            if(digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0; // 如果是 0，循环会起到进位的作用。
        }
        int[] newNumber = new int[digits.length + 1]; // 如果循环没有 return，说明都是 0，手动在最前面 +1。
        newNumber[0] = 1;
        return newNumber;
    }
}

Introduction to 2D Array

Similar to a one-dimensional array, a two-dimensional array also consists of a sequence of elements. But the elements can be laid out in a rectangular grid rather than a line.

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
public class Main {
    private static void printArray(int[][] a) {
        for (int i = 0; i < a.length; ++i) {
            System.out.println(a[i]);  // 打印地址！！！
        }
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; a[i] != null && j < a[i].length; ++j) { // a[i] != null!!!
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.println("Example I:");
        int[][] a = new int[2][5];
        printArray(a);
        System.out.println("Example II:");
        int[][] b = new int[2][];
        printArray(b); // 会打出来 null！！！
        System.out.println("Example III:");
        b[0] = new int[3];
        b[1] = new int[5];
        printArray(b);
        int[][] c;
        c = new int[3][4];
        printArray(c);
        int[] d[] = new int[2][3];
        printArray(d);
    }
}

Question - Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

1
2
3
4
5
6
7
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,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
26
27
28
29
30
31
32
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> out = new ArrayList<>();
        if(matrix.length == 0 || matrix[0].length == 0) return out;
        int top = 0, left = 0;
        int bottom = matrix.length - 1;
        int right = matrix[0].length - 1;
        while(top <= bottom || left <= right){
            for (int i = left; i <= right; i++){
                out.add(matrix[top][i]);
            }
            top++;
            if(left > right || top > bottom) break;
            for (int j = top; j <= bottom; j++){
                out.add(matrix[j][right]);
            }
            right--;
            if(left > right || top > bottom) break;
            for (int k = right; k >= left; k--){
                out.add(matrix[bottom][k]);
            }
            bottom--;
            if(left > right || top > bottom) break;
            for (int l = bottom; l >= top; l--){
                out.add(matrix[l][left]);
            }
            left++;
            if(left > right || top > bottom) break;
        }
        return out;
    }
}

Question - Pascal's Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> allRows = new ArrayList<List<Integer>>();
        List<Integer> row = new ArrayList<Integer>();
        for(int i = 0; i < numRows; i++) {
            row.add(1); // 每一行最后新增一个 1
            for(int j = row.size()-2; j >= 1; j--) //从第三行开始，中间(除了最后一个和第一个)的数等于自己加前一个数
                row.set(j, row.get(j) + row.get(j - 1));
            allRows.add(new ArrayList<Integer>(row));
        }
        return allRows;
    }
}

Introduction to String

A string is actually an array of unicode characters. You can perform almost all the operations we used in an array. You can try it out by yourself.

However, there are some differences.

Compare Function

String has its own compare function (we will show you the usage of compare function in the code below).

Can we use "==" to compare two strings?

It depends on the answer to the question:

Does the language support operator overloading?

  1. If the answer is yes (like C++), we may use == to compare two strings.
  2. If the answer is no (like Java), we may not use == to compare two strings. When we use ==, it actually compares whether these two objects are the same object.
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
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // initialize
        String s1 = "Hello World";
        System.out.println("s1 is \"" + s1 + "\"");
        String s2 = s1;
        System.out.println("s2 is another reference to s1.");
        String s3 = new String(s1);
        System.out.println("s3 is a copy of s1.");
        // compare using '=='
        System.out.println("Compared by '==':");
        // true since string is immutable and s1 is binded to "Hello World"
        System.out.println("s1 and \"Hello World\": " + (s1 == "Hello World"));
        // true since s1 and s2 is the reference of the same object
        System.out.println("s1 and s2: " + (s1 == s2));
        // false since s3 is refered to another new object
        System.out.println("s1 and s3: " + (s1 == s3));
        // compare using 'equals'
        System.out.println("Compared by 'equals':");
        System.out.println("s1 and \"Hello World\": " + s1.equals("Hello World"));
        System.out.println("s1 and s2: " + s1.equals(s2));
        System.out.println("s1 and s3: " + s1.equals(s3));
        // compare using 'compareTo'
        System.out.println("Compared by 'compareTo':");
        System.out.println("s1 and \"Hello World\": " + (s1.compareTo("Hello World") == 0));
        System.out.println("s1 and s2: " + (s1.compareTo(s2) == 0));
        System.out.println("s1 and s3: " + (s1.compareTo(s3) == 0));
    }
}

Immutable or Mutable

Immutable means that you can't change the content of the string once it's initialized.

  1. In some languages (like C++), the string is mutable. That is to say, you can modify the string just like what you did in an array.
  2. In some other languages (like Java), the string is immutable. This feature will bring several problems. We will illustrate the problems and solutions in the next article.

You can determine whether the string in your favorite language is immutable or mutable by testing the modification operation. Here is an example:

1
2
3
4
5
6
7
8
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s1 = "Hello World";
        s1[5] = ','; // Line 5: error: array required, but String found
        System.out.println(s1);
    }
}

Extra Operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s1 = "Hello World";
        // 1. concatenate
        s1 += "!";
        System.out.println(s1); // Hello World!
        // 2. find
        System.out.println("The position of first 'o' is: " + s1.indexOf('o')); // The position of first 'o' is: 4
        System.out.println("The position of last 'o' is: " + s1.lastIndexOf('o')); // The position of last 'o' is: 7
        // 3. get substring
        System.out.println(s1.substring(6, 11)); // World
    }
}

You should be aware of the time complexity of these built-in operations.

For instance, if the length of the string is NN, the time complexity of both finding operation and substring operation is O(N)O(N).

Also, in languages which the string is immutable, you should be careful with the concatenation operation (we will explain this in next article as well).

Never forget to take the time complexity of built-in operations into consideration when you compute the time complexity for your solution.

Immutable String - Problems & Solutions

You should know whether the string in your favorite language is immutable or not in the previous article. If the string is immutable, it will bring some problems. Hopefully, we will also provide the solution at the end.

Obviously, an immutable string cannot be modified. If you want to modify just one of the characters, you have to create a new string.

You should be very careful with string concatenation. Let's look at an example when we do string concatenation repeatedly in a for loop:

1
2
3
4
5
6
7
8
9
10
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}

Notice how slow string concatenation is for Java? On the other hand, there is no noticeable performance impact in C++.

In Java, since the string is immutable, concatenation works by first allocating enough space for the new string, copy the contents from the old string and append to the new string.

Therefore, the time complexity in total will be:
5+5×2+5×3+…+5×n=5×(1+2+3+…+n)=5×n×(n+1)/2 5 + 5 × 2 + 5 × 3 + … + 5 × n = 5 × (1 + 2 + 3 + … + n) = 5 × n × (n + 1) / 2

which is O(n2)O(n2).

If you want your string to be mutable, there are some substitutions:

  1. If you did want your string to be mutable, you can convert it to a char array.
1
2
3
4
5
6
7
8
9
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        String s = "Hello World";
        char[] str = s.toCharArray();
        str[5] = ',';
        System.out.println(str);
    }
}
  1. If you have to concatenate strings often, it will be better to use some other data structures like StringBuilder. The below code runs in O(n)O(n) complexity.
1
2
3
4
5
6
7
8
9
10
11
// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        int n = 10000;
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            str.append("hello");
        }
        String s = str.toString();
    }
}

Question - Add Binary

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 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
// 位数操作，加法进位问题！！！
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0; // 用来标记是否进位！！！
        while (i >= 0 || j >= 0){
            int sum = carry;
            if (i >= 0){
                sum += a.charAt(i--) - '0'; // charAt - '0' 可以得到 int。类似 charAt - 'a' ！！！
            }
            if (j >= 0){
                sum += b.charAt(j--) - '0';
            }
            result.append(sum % 2); // sum % 2 得结果！！！
            carry = sum / 2; /// sum / 2 得进位 ！！！
        }
        if (carry == 1){
            result.append(carry);
        } // 如果最后有进位，直接加入数组！！！
        return result.reverse().toString(); // 从前往后和从后往前操作相等？？？
    }
}

Question - Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

1
2
Input: haystack = "hello", needle = "ll"
Output: 2
1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1
1
2
3
4
5
6
7
8
9
public int strStr(String haystack, String needle) {
    for (int i = 0; ; i++) {
        for (int j = 0; ; j++) { // 死循环！！！
            if (j == needle.length()) return i; // 在 heystack 里找到了 needle！！！
            if (i + j == haystack.length()) return -1; // 超出了 haystack 还未找到！！！
            if (needle.charAt(j) != haystack.charAt(i + j)) break; // 不相等直接跳出，j 从零开始！！！
        }
    }
}

Question - Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

1
2
Input: ["flower","flow","flight"]
Output: "fl"
1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
1
2
3
4
5
6
7
8
9
public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String pre = strs[0]; // pre 为第一个 string
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(pre) != 0) // 查找 pre（第一个数组）是否在后面的数组中出现。indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置！！！
                pre = pre.substring(0, pre.length() - 1); // 用 substring 方法缩减 pre
        }
        return pre;
    }

Two-pointer Technique - Scenario I !!!

In the previous chapter, we solve some problems by iterating the array. Typically, we only use one pointer starting from the first element and ending at the last one to do iteration. However, sometimes, we might need to use two pointers at the same time to do the iteration.

An Example

Let's start with a classic problem:

Reverse the elements in an array.

The idea is to swap the first element with the end, advance to the next element and swapping repeatedly until it reaches the middle position.

We can use two pointers at the same time to do the iteration: one starts from the first element and another starts from the last element. Continue swapping the elements until the two pointers meet each other.

1
2
3
4
5
6
7
8
9
public static void reverse(int[] v, int N) {
    int i = 0;
    int j = N - 1;
    while (i < j) {
        swap(v, i, j);  // this is a self-defined function
        i++;
        j--;
    }
}

Summary

To summarize, one of the typical scenarios to use two-pointer technique is that you want to

Iterate the array from two ends to the middle.

So you can use the two-pointer technique:

One pointer starts from the beginning while the other pointer starts from the end.

And it is worth noting that this technique is often used in a sorted array.

Question - Reverse String

Write a function that takes a string as input and returns the string reversed.

1
2
Input: "A man, a plan, a canal: Panama"
Output: "amanaP :lanac a ,nalp a ,nam A"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public String reverseString(String s) {
        char[] word = s.toCharArray();
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            char temp = word[i];
            word[i] = word[j];
            word[j] = temp;
            i++;
            j--;
        }
        return new String(word);
    }
}
1
2
3
4
5
6
class Solution {
    public String reverseString(String s) {
        StringBuilder sb = new StringBuilder(s);
        return sb.reverse().toString();
    }
}

Question - Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

1
2
3
4
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int result = 0;
        for (int i = 0; i < nums.length; i += 2){
            result += nums[i];
        }
        return result;
    }
}

How to use Two-pointer Technique???

Question - Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] twoSum(int[] num, int target) {
    int[] indice = new int[2];
    if (num == null || num.length < 2) return indice;
    int left = 0, right = num.length - 1;
    while (left < right) {
        int v = num[left] + num[right];
        if (v == target) {
            indice[0] = left + 1;
            indice[1] = right + 1;
            break;
        } else if (v > target) {
            right --;
        } else {
            left ++;
        }
    }
    return indice;
}

Two-pointer Technique - Scenario II

Sometimes, we can use two pointers with different steps to solve problems.

An Example

Let's start with another classic problem:

Given an array and a value, remove all instances of that value in-place and return the new length.

If we don't have the limitation of space complexity, it will be easier. We can initialize a new array to store the answer. Iterate the original array and add the element to the new array if the element is not equal to the given target value.

Actually, it is equivalent to using two pointers, one is used for the iteration of the original array and another one always points at the last position of the new array.

Reconsider the Space Limitation

Now let's reconsider the space limitation.

We can use a similar strategy. We still use two pointers: one is still used for the iteration while the second one always points at the position for next addition.

Here is the code for your reference:

1
2
3
4
5
6
7
8
9
10
public int removeElement(int[] nums, int val) {
    int k = 0;
    for (int i = 0; i < nums.length; ++i) {
        if (nums[i] != val) {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
}

We use two pointers, one faster-runner i and one slower-runner k, in the example above. i moves one step each time while k moves one step only if a new needed value is added.

Summary

This is a very common scenario of using the two-pointer technique when you need:

One slow-runner and one fast-runner at the same time.

The key to solving this kind of problems is to

Determine the movement strategy for both pointers.

Similar to the previous scenario, you might sometimes need to sort the array before using the two-pointer technique. And you might need a greedy thought to determine your movement strategy.

Question - Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1)O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int removeElement(int[] nums, int val) {
        int j = 0;
        for (int i = 0; i < nums.length; ++i){
            if (nums[i] != val){
                nums[j++] = nums[i];
            }
        }
        return j;
    }
}

Question - Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

1
2
3
4
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int counter = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == 1){
                counter++;
            } else{
                counter = 0;
            }
            if (counter > max){
                max = counter;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
public int findMaxConsecutiveOnes(int[] nums) {
        int maxHere = 0, max = 0;
        for (int n : nums)
            max = Math.max(max, maxHere = n == 0 ? 0 : maxHere + 1);
        return max;
}

Question - Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

1
2
3
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
  
        int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
  
        while (j < nums.length) {  // Sliding windows!!!
            sum += nums[j++];
            while (sum >= s) {
                min = Math.min(min, j - i); // 从 i 到 j!!!
                sum -= nums[i++];
            }
        }
        return min == Integer.MAX_VALUE? 0 : min;
    }
}