一、什么是数组？

数组由相同类型的元素（element）的集合所组成的结构
分配一块连续的内存来存储元素
利用元素的索引（index）可以计算出该元素对应的储存地址

二、数组Array的特性

在内存中为连续空间，定址公式： addr(curElem) = addr(intialElem) +sizeof(curElem) * index
存储在数组中的元素是相同类型的
通过index获取数组元素的时间复杂度为O(1)

三、ArrayList的实现

Java中的声明: ArrayList list = new ArrayList();
基本操作

ArrayList基本操作API

利用数组作为存储
初始化时需要指定ArrayList的容量
记得边界检查
当达到数组容量时再添加新元素时,需要resize操作对底层数组进行扩容

附上实现代码:

public class ArrayList {
    private int capacity;
    private int size;
    private int[] data;

    public ArrayList(int capacity){
        this.capacity = capacity;
        this.size = 0;
        this.data = new int[capacity];
    }

    public int get(int index){
        if(index<0 || index>size){
            //throw Exception
        }
        return data[index];
    }

    public void set(int index,int value){
        if(index<0 || index>size){
            //throw Exception
        }
        data[index] = value;
    }

    public void add(int index , int value){
        if(index < 0 || index > size){
            //throw Exception
        }
        if(size == capacity){ 
            resize();
        }
        size++;
        for(int i = size -1; i>= index+1;i--){
            data[i] = data[i-1];
        }
        data[index] = value;
    }

    public void remove(int index){
        if(index < 0 || index > size){
            //throw Exception
        }
        size--;
        for(int i = index;i<size;i++){
            data[i] = data[i+1];
        }
    }

    private void resize(){
        capacity*=2;
        int[] new_data = new int[capacity];
        for(int i = 0;i<size;i++){
            new_data[i] = data[i];
        }
        data = new_data;
    }

四、例题

1、两数之和

两数之和

思路1 ：暴力遍历，遍历取一个数，计算它与其它数字之和，遍历全部情况得到想要的结果对。时间复杂度为: O(n2)

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

思路2 ：排序 + 两根指针

public int[] twoSum(int[] nums,int target) {
    int[] result = new int[2];
    Arrays.sort(nums);
    int start = 0, end = nums.length -1;
    while(start < end){
        if(nums[start] + nums[end] == target){
            result[0] = nums[start];
            result[1] = nums[end];
            return result;
        }       
        if(nums[start] + nums[end] > target){
            end--;
        }       
        if(nums[start] + nums[end] < target){
            start++;
        }
    }
    return result;
}

核心想法：如果现在两根指针所指元素之和大于目标值，则表明现在两数之和过大，应使end指针指向更小的数，即索引减小（end–），反之则表明现在两数之和过小，应使start指针指向更大的数，即索引增加（start++）
通过对数组排序与两根指针组合，减少无意义的遍历
时间复杂度分析：排序： O(nlogn), 两根指针算法：O(n)
时间复杂度： O(nlogn) + O(n) = O(nlogn)

2、三数之和

三数之和

思路1 ：当然可以用暴力遍历求解，时间复杂度为O(n3)

思路2 ：排序 + 两根指针算法求解O(n2)

public int[] threeSum(int[] nums, int target) {
    int[] result = new int[3];
    if(nums.length < 3) return nums;
    Arrays.sort(nums);
    for(int i =0; i < nums.length-2;i++){
        int start = i+1,end = nums.length-1,new_target = target-nums[i];
        while (start < end) {
            if (nums[start] + nums[end] == new_target) {
                result[0] = nums[start];
                result[1] = nums[end];
                result[2] = nums[i];
                return result;
            }
            if (nums[start] + nums[end] > new_target) {
                end--;
            }
            if (nums[start] + nums[end] < new_target) {
                start++;
            }
        }
    }
    return result;
}

遍历第一个数字num1，看看另外两数之和是否能满足target – num1，这就转化为两数之和的问题
时间复杂度：O(nlogn) + n * O(n) =O(n2)

3、K-Sum解法总结

排序
尝试遍历第一个数，将问题转化为 k–1 Sum
2-Sum: O(nlogn) + O(n) = O(nlogn)
3-Sum: O(nlogn) + O(n2) = O(n2)
4-Sum: O(nlogn) + O(n3) = O(n3)
k-Sum: O(nlogn) + O(nk-1) = O(nk-1)

四数之和举例：

public int[] fourSum(int[] nums, int target) {
    int[] result = new int[4];
    if(nums.length < 4) return nums;
    Arrays.sort(nums);
    for(int i =0; i < nums.length-2;i++){
        for(int j = i+1 ; j<nums.length-3;j++){
            int start = j+1,end = nums.length-1,new_target = target-nums[i]-nums[j];
            while (start < end) {
                if (nums[start] + nums[end] == new_target) {
                    result[0] = nums[start];
                    result[1] = nums[end];
                    result[2] = nums[i];
                    result[3] = nums[j];
                    return result;
                }
                if (nums[start] + nums[end] > new_target) {
                    end--;
                }
                if (nums[start] + nums[end] < new_target) {
                    start++;
                }
            }
        }
    }
    return result;
}

4、反转数组

给定一个数组，反转数组中所有的数字，例如：Input:{1,2,3,4,5},Output:{5,4,3,2,1}

public void reverseArray(int[] nums) {
        int start = 0 , end = nums.length - 1;
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
}

思路：双指针，首尾交换，时间复杂度O(n)

5、奇数偶数排序

给定一组整数，对它们进行排序，以便所有奇数整数在偶数整数之前出现。元素的顺序可以改变。排序的奇数和偶数的顺序无关紧要。例如：Input:{4,3,5,2,1,11,0},Output:{9,3,5,11,0,2,4}

public void oddEvenSort(int[] nums) {
        int first = 0 , second = nums.length - 1;
        while(first < second){
            // 奇数的话，第一根指针就往后面移动一位，直到为偶数停下来
            while(first < second && nums[first] % 2==1){
                first++;
            }
            // 偶数的话，第二根指针就往前移动一位，直到为奇数停下
            while(first < second && nums[first] % 2==0){
                second--;
            }
            if(first < second){
                int temp = nums[first];
                nums[first] = nums[second];
                nums[second] = temp;
                first++;
                second--;
            }
        }
}

思路：双指针，在一定条件下进行首尾交换，时间复杂度O(n)

6、合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，请按递增顺序将它们合并到一个排序数组中。例如：Input: {1, 3, 5}, {2, 4, 6}，Output: {1, 2, 3, 4, 5, 6}

思路1：对两个数组合并O(n),合并后排序O(nlogn),时间复杂度：O(n)+O(nlogn)=0(nlogn)

思路2：双指针 O(n)

public int[] merge(int[] arr1,int[] arr2){
    int[] result = new int[arr1.length + arr2.length];
    int index=0,index1=0,index2=0;
    while(index1 < arr1.length && index2 < arr2.length){
        if(arr1[index1]<arr2[index2]){
            result[index++] = arr1[index1++];
        }else{
            result[index++] = arr2[index2++];
        }
    }
    for(int i = index1;i<arr1.length;i++){
        result[index++] = arr1[i];
    }

    for(int i = index2;i<arr2.length;i++){
        result[index++] = arr2[i];
    }
    return result;
}