Array & Hash 🌼

Note

Interface

An interface is a completely “abstract class“ that is used to group related methods with empty bodies

1
2
3
4
5
// interface
interface Animal {
  public void animalSound(); // interface method (does not have a body)
  public void run(); // interface method (does not have a body)
}

To access the interface methods, the interface must be “implemented” (kinda like inherited) by another class with the implements keyword (instead of extends). The body of the interface method is provided by the “implement” class:

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
// Interface
interface Animal {
  public void animalSound(); // interface method (does not have a body)
  public void sleep(); // interface method (does not have a body)
}

// Pig "implements" the Animal interface
class Pig implements Animal {
  public void animalSound() {
    // The body of animalSound() is provided here
    System.out.println("The pig says: wee wee");
  }
  public void sleep() {
    // The body of sleep() is provided here
    System.out.println("Zzz");
  }
}

class Main {
  public static void main(String[] args) {
    Pig myPig = new Pig();  // Create a Pig object
    myPig.animalSound();
    myPig.sleep();
  }
}

Notes on Interfaces:

  • Like abstract classes, interfaces cannot be used to create objects (in the example above, it is not possible to create an “Animal” object in the MyMainClass)
  • Interface methods do not have a body - the body is provided by the “implement” class
  • On implementation of an interface, you must override all of its methods
  • Interface methods are by default abstract and public
  • Interface attributes are by default public, static and final
  • An interface cannot contain a constructor (as it cannot be used to create objects)

Why And When To Use Interfaces?

  1. To achieve security - hide certain details and only show the important details of an object (interface).

  2. Java does not support “multiple inheritance” (a class can only inherit from one superclass). However, it can be achieved with interfaces, because the class can implement multiple interfaces. Note: To implement multiple interfaces, separate them with a comma (see example below).

Lambda expression

Lambda Expressions were added in Java 8.

A lambda expression is a short block of code which takes in parameters and returns a value. Lambda expressions are similar to methods, but they do not need a name and they can be implemented right in the body of a method.

Syntax

The simplest lambda expression contains a single parameter and an expression:

1
parameter -> expression

To use more than one parameter, wrap them in parentheses:

1
(parameter1, parameter2) -> expression

Expressions are limited. They have to immediately return a value, and they cannot contain variables, assignments or statements such as if or for. In order to do more complex operations, a code block can be used with curly braces. If the lambda expression needs to return a value, then the code block should have a return statement.

1
(parameter1, parameter2) -> { code block }

Example

Use a lambda expression in the ArrayList‘s forEach() method to print every item in the list:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();
    numbers.add(5);
    numbers.add(9);
    numbers.add(8);
    numbers.add(1);
    numbers.forEach( (n) -> { System.out.println(n); } );
  }
}

output:
5
9
8
1

To use a lambda expression in a method, the method should have a parameter with a single-method interface as its type. Calling the interface’s method will run the lambda expression:

Example

Create a method which takes a lambda expression as a parameter:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
interface StringFunction {
  String run(String str);
}

public class Main {
  public static void main(String[] args) {
    StringFunction exclaim = (s) -> s + "!";   
    StringFunction ask = (s) -> s + "?";
    printFormatted("Hello", exclaim);
    printFormatted("Hello", ask);
  }
  public static void printFormatted(String str, StringFunction format) {
    String result = format.run(str);
    System.out.println(result);
  }
}


Hello!
Hello?

Double colon :: operator

They behave exactly as the lambda expressions. The only difference it has from lambda expressions is that this uses direct reference to the method by name instead of providing a delegate to the method.

Syntax:

1
<Class name>::<method name>

Example: To print all elements of the stream:

  • Using Lambda expression:

    1
    stream.forEach( s-> System.out.println(s));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Java code to print the elements of Stream
// without using double colon operator
 
import java.util.stream.*;
 
class GFG {
  public static void `main(String[] args)
  {
 
    // Get the stream
    Stream<String> stream
      = Stream.of("Geeks", "For",
            "Geeks", "A",
            "Computer",
            "Portal");
 
    // Print the stream
    stream.forEach(s -> System.out.println(s));
  }
}

Output:

1
2
3
4
5
6
Geeks
For
Geeks
A
Computer
Portal

Using double colon operator:

1
stream.forEach( System.out::println);

When and how to use double colon operator?

Method reference or double colon operator can be used to refer:

  • a static method,
  • an instance method, or
  • a constructor.

How to use method reference in Java:

  1. Static method

    Syntax:

    1
    (ClassName::methodName)

    Example:

    1
    SomeClass::someStaticMethod
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
// Java code to show use of double colon operator
// for static methods

import java.util.*;

class GFG {

	// static function to be called
	static void someFunction(String s)
	{
		System.out.println(s);
	}

	public static void main(String[] args)
	{

		List<String> list = new ArrayList<String>();
		list.add("Geeks");
		list.add("For");
		list.add("GEEKS");

		// call the static method
		// using double colon operator
		list.forEach(GFG::someFunction);
	}
}

Output:

1
2
3
Geeks
For
GEEKS
  1. Instance method

Syntax:

1
(objectOfClass::methodName)

Example:

1
System.out::println

Program:

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
// Java code to show use of double colon operator
// for instance methods

import java.util.*;

class GFG {

	// instance function to be called
	void someFunction(String s)
	{
		System.out.println(s);
	}

	public static void main(String[] args)
	{

		List<String> list = new ArrayList<String>();
		list.add("Geeks");
		list.add("For");
		list.add("GEEKS");

		// call the instance method
		// using double colon operator
		list.forEach((new GFG())::someFunction);
	}
}

Output:

1
2
3
Geeks
For
GEEKS

https://www.geeksforgeeks.org/double-colon-operator-in-java/

Leetcode

1. Two Sum

Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

1
2
Input: nums = [3,3], target = 6
Output: [0,1]

🌟Coding:

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
class Solution {
O(n)
  public int[] twoSum(int[] nums, int target) { 
      // use HashMap to record the values in num and the order of num[i]
      // also HashMap can find elements fast ,using containsKey containsValue function
            HashMap<Integer, Integer> map = new HashMap<>();

            for(int i = 0; i < nums.length; i++){
                if(map.containsKey(target - nums[i])){
                    return new int[]{map.get(target - nums[i]), i};
                }else{
                    map.put(nums[i],i);
                }
            }
            return new int[]{};

  }

}


O(n^2)
class Solution {
    public int[] twoSum(int[] nums, int target) {

        for(int i = 0; i < nums.length - 1 ; i++){
            for(int j = i + 1; j < nums.length; j ++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }
}

49. Group Anagrams

Medium

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1
2
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

1
2
Input: strs = [""]
Output: [[""]]

Example 3:

1
2
Input: strs = ["a"]
Output: [["a"]]

🌟Coding:

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 List<List<String>> groupAnagrams(String[] strs) {
        //returned value
        List<List<String>> res = new ArrayList<>();
        // check input 
        if (strs.length == 0) return res;
        // Use computeIfAbsent of HashMap to check if it has previous anagrams
        // String -> int[] Hash; List<String> -> String s
        HashMap<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            // use int array to record component letters of each s 
            int[] hash = new int[26];
            for (char c : s.toCharArray()) {
                hash[c - 'a']++;
            }
            // turn int array into string so we can compare if there's same key
            // if we don't turn into string here then we need to do a loop for 26 times to see if there's a same hash before which is not worth it
            String key = new String(Arrays.toString(hash)); 🌟
            //use computeIfAbsent to see if there's a anagram of s before 
            // if no then create a new arraylist in value
            // if yes then computeIfAbsent won't do anything
            map.computeIfAbsent(key, k -> new ArrayList<>()); 🌟🌟 
            // s will be added to the existing arraylist
            map.get(key).add(s); 🌟
        }
        // values of the HashMap(trype: List<String>) are the answer
        res.addAll(map.values()); 🌟
        return res;
    }
}

⭕ For List, it’s addAll;

​ For HashMap, it’s putAll

⭕ List<List> res = new ArrayList<>(); remember there’s a parenthesis

⭕ It’s Arrays.toString(hash), instead of hash.Arrays.toString()

1
2
map.computeIfAbsent(key, k -> new ArrayList<>()); 
map.get(key).add(s);

the above is equal to the following:

1
2
3
4
5
if(! map.containsKey(mid)){
	List<String> x = new ArrayList<>();
   map.put(mid, x);
 }
 map.get(mid).add(s);

347. Top K Frequent Elements

Medium

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

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 Solution3 {
     /**
     * Time Complexity: O(n)
     * Space Complexity: O(n)
     */
     public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>(); 
        //key: number. value: times of number appeared
        List<Integer> bucket[] = new ArrayList[nums.length + 1];                		// sort map's value
        
        for (int num : nums)
            count.merge(num, 1, Integer::sum); // calculate times
        
        for (int key : count.keySet()){
            int freq = count.get(key);
            if (bucket[freq] == null)
                bucket[freq] = new ArrayList<>(); 
            bucket[freq].add(key);
        }
        
        int index = 0;
        int[] res = new int[k];
        for (int i = nums.length; i >= 0; i--)
            if (bucket[i] != null)
                for (int val : bucket[i]){
                    res[index++] = val;
                    if(index == k)
                        return res;
                }
        return res;
    }

⭕ The syntax of the merge() method is:

1
hashmap.merge(key, value, BiFunction remappingFunction)

Parameters: This method accepts three parameters:

  • Key: which is the key for which we have a particular value. If two keys have the same value they are merged.
  • Value: which is the index corresponding to the particular key which is stored in the bucket.
  • BiFunction: which is the function having two arguments to be used for calculating the new mapping from the old value and given value.

Return Value: This method returns the key along with its value if the key is not present or is associated with null. Else if the key already holds any value, it merges the old value with the new value using the mapping technique.

Array:

Easy

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

1
2
3
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
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
class Solution {
    int res = -1;
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        backtrack(nums, target, start, end);
        return res;
    }
    public void backtrack(int[] nums, int target, int start, int end){
        if(start <= end) {
            int mid = start + (end - start) / 2;;
            if(target > nums[mid]){
                backtrack(nums, target, mid+1, end);
            }else if( target  < nums[mid]){
                backtrack(nums, target, start, mid-1);
            }else{
                res = mid;
            }
        }
    }
}




class Solution {
    public int search(int[] nums, int target) {
       int start = 0;
       int end  = nums.length - 1;
       if(nums.length == 1){
           if(nums[0] == target) return 0;
           return -1;
       }
       while(start <= end){ //!!! notice it's not start != end
            int mid = (start + end)/2;
            if(nums[mid] == target){
                return mid;
            }else{
                if(nums[mid] > target){
                    end = mid - 1;
                }else{
                    start = mid + 1;
                }
            }
       } 
       
       return -1;
    }
}

Wrong version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int res = 0;
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        backtrack(nums, target, start, end);
        return res;
    }
    public void backtrack(int[] nums, int target, int start, int end){
        if(start > end) res = -1;  //!!!!
        int mid = (start + end)/2; //!!!!
        if(target > nums[mid]){
            backtrack(nums, target, mid, end);  //!!!!
        }else if( target  < nums[mid]){
            backtrack(nums, target, start, mid); //!!!!
        }else{
            res = mid;
        }
    }
}

leedcode master:

!!!!!!!!!!!!!!!!! 二分法第1种写法

我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

  • while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
  • if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

左闭右闭区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

!!!!!!!!!!!!!!!!! 二分法第二种写法

如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

  • while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

27. Remove Element

Easy

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • Return k.

Example 1:

1
2
3
4
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int flag = 0;
        for(int i =0; i<nums.length; i++){
            if(nums[i] != val){
                nums[flag] = nums[i];
                flag ++;
            }
        } 
        return flag;  
    }
}

844. Backspace String Compare

Easy

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

1
2
3
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

wrong version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] s_ = s.toCharArray();
        char[] t_ = t.toCharArray();
        return backspace(s_).equals(backspace(t_));
    }

    public String backspace(char[] s){
        int flag = 0;
        for(int i = 0; i < s.length; i++){
            if(s[i] != '#'){
                s[flag] = s[i];
                flag ++;
            }
        }
        return new String(s, 0, flag); //flag is exclusive
    }
}

correct:

  • two pointers:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] s_ = s.toCharArray();
        char[] t_ = t.toCharArray(); //!!!!!
        return backspace(s_).equals(backspace(t_)); //!!!!
    }

    public String backspace(char[] s){
        int flag = 0;
        for(int i = 0; i < s.length; i++){
            if(s[i] != '#'){
                s[flag] = s[i];
                flag ++;
            }else{
                flag--;   //!!!!!
                if(flag < 0) flag = 0; //!!!!!!!!!!!!!!
            }
        }
        return new String(s, 0, flag); //flag is exclusive !!!
    }
}

  • stack:

    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

    // string builder
    class Solution {
        public boolean backspaceCompare(String s, String t) {
            StringBuilder ssb = new StringBuilder(); // 模拟栈
            StringBuilder tsb = new StringBuilder(); // 模拟栈
            // 分别处理两个 String
            for (char c : s.toCharArray()) {
                if (c != '#') {
                    ssb.append(c); // 模拟入栈
                } else if (ssb.length() > 0){ // 栈非空才能弹栈
                    ssb.deleteCharAt(ssb.length() - 1); // 模拟弹栈
                }
            }
            for (char c : t.toCharArray()) {
                if (c != '#') {
                    tsb.append(c); // 模拟入栈
                } else if (tsb.length() > 0){ // 栈非空才能弹栈
                    tsb.deleteCharAt(tsb.length() - 1); // 模拟弹栈
                }
            }
            return ssb.toString().equals(tsb.toString());
        }
    }




    // stack

    class Solution {
        public boolean backspaceCompare(String s, String t) {
            return buildStack(s).equals(buildStack(t));
        }

        private Stack<Character> buildStack(String str) {
            Stack<Character> stack = new Stack<>();
            for (char c : str.toCharArray()) {
                if (c != '#') {
                    stack.push(c);
                } else if (!stack.isEmpty()) {
                    stack.pop();
                }
            }
            return stack;
        }
    }

    977. Squares of a Sorted Array

    Easy

    Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

    Example 1:

    1
    2
    3
    4
    Input: nums = [-4,-1,0,3,10]
    Output: [0,1,9,16,100]
    Explanation: After squaring, the array becomes [16,1,0,9,100].
    After sorting, it becomes [0,1,9,16,100].
    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
    easy way:
    class Solution {
        public int[] sortedSquares(int[] nums) {
            for(int i = 0; i < nums.length; i++){
                nums[i] = nums[i] * nums[i];
            }
            Arrays.sort(nums);
            return nums;
        }
    }



    two pointers:
    //leetcode master version
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int left = 0;
            int right = nums.length - 1;
            int index = nums.length - 1;
            int[] result = new int[nums.length];
            while(left <= right){
                if(nums[left] * nums[left] < nums[right] * nums[right]){
                    result[index] = nums[right] * nums[right];
                    index--;
                    right --;
                }else{
                    result[index] = nums[left] * nums[left];
                    index--;
                    left ++;
                }
            }
            return result;
    ;
        }
    }
    // my verison
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int[] res = new int[nums.length];
            int left = 0 ;
            int right = nums.length - 1;
            for(int i = nums.length - 1 ; i >= 0; i--){
                if(nums[left]*nums[left] <= nums[right]*nums[right]){
                    res[i] = nums[right]*nums[right];
                    right --;
                }else{
                    res[i] = nums[left]*nums[left];
                    left ++;
                }
            }
            return res;
        }
    }


    two pointer(Wrong):
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int[] res = new int[nums.length];
            int left = 0 ;
            int right = nums.length - 1;
            for(int i = 0 ; i < res.length; i++){
                if(nums[left]*nums[left] <= nums[right]*nums[right]){
                    res[i] = nums[left]*nums[left];
                    left ++;
                }else{
                    res[i] = nums[right]*nums[right];
                    right --;
                }
            }
            return res;
        }
    }

    双指针法

    数组其实是有序的， 只不过负数平方之后可能成为最大数了。

    那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

    此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

    定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

    如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

    如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

img

209. Minimum Size Subarray Sum

  • sliding window

Medium

Given an array of positive integers nums and a positive integer target, return the minimal length of a

subarray

whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

1
2
3
Input: target = 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
18
19
20
21
22
23
24
不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。


//leetcode master
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        for(int right = 0; right < nums.length; right++){
            sum += nums[right];
            if(sum >= target){
                while(sum >= target){ //notice here's while not if
                    res = Math.min(res, right - left + 1);
                    sum -= nums[left];
                    left ++;
                }
            }
        }
        if(res == Integer.MAX_VALUE) return 0;
        return res;

    }
}

okay, so for sliding window, you move the right border first, once the sum is bigger than the target, then you move the left border until the sum is smaller than the target. once the sum is smaller, then once again move the right border.

这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：

209.长度最小的子数组

59. Spiral Matrix II

Medium

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:

img

1
2
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.md

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
// leetcode master
class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;  // 控制循环次数
        int[][] res = new int[n][n];
        int start = 0;  // 每次循环的开始点(start, start)
        int count = 1;  // 定义填充数字
        int i, j;

        while (loop++ < n / 2) { // 判断边界后，loop从1开始
            // 模拟上侧从左到右
            // 注意这四个循环的循环条件
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }

            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }

            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }

            // 模拟左侧从下到上
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }

        if (n % 2 == 1) {
            res[start][start] = count;
        }

        return res;
    }
}


//my version:
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int start = 0;
        int loop = 0;
        int count = 1;
        int i,j;
        while(loop < n/2){
            for(j = start; j < n - loop - 1; j++){
                res[start][j] = count++;
            }
            for(i = start; i < n - loop - 1; i++){
                res[i][j] = count++;
            }
            for(; j > loop ; j --){
                res[i][j] = count++;
            }
            for(; i > loop ; i --){
                res[i][j] = count++;
            }
            start++;
            loop++;
            
        }

        if(n%2 == 1){
                res[n/2][n/2] = count++;
        }

        return res;

    }
    
}

[toc]