2.2 Arrays

Java Array Method

// create
int[] arr = new int[10];
// length
int len = arr.length;
// set
arr[0] = 99;
// get
int e = arr[0];
// sort
arr = Arrays.sort(arr);

// 2d array
// 创建 5 行 10 列的二维数组
int[][] arrTwo = new int[5][10];
// 第一行，第二列
int[0][1] = 1;
// 第二行，第一列
int[1][0] = 2;
// 获取行列长度
int lenRow = arrTwo.length;
int lenCol = arrTwo[0].length;
// 遍历二维数组
for (int i = 0; i < arrTwo.length; i++) {
    for (int j = 0; j < arrTwo[i].length; j++) {
        System.out.print(arrTwo[i][j] + " ");
    }
    System.out.println();
}

Example

2 Sum: given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution 1: two for loops

• time：O(n^2)
• space: O(1)

Solution 2: one for loops + HashMap

• time: O(n)
• space: O(n)
• trick:  construct HashMap in the same for loop

Solution 3: sort the array + two pointer

• time: O(nlogn)，即快排的时间复杂度
• space: O(1)

// HashMap solution
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) return null;

        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            int remaining = target - numbers[i];
            if (map.containsKey(remaining)) {
                result[1] = i;
                result[0] = map.get(remaining);
                return result;
            }
            map.put(numbers[i], i);
        }
        return result;
    }
}

扩展：3 Sum: sort + one for loop + two pointer

https://zhuanlan.zhihu.com/p/104800339