数组部分

[huangchucai]

数组

注意点

1. 输入是否合法
2. 数组是否排序
3. 是否重复元素
4. 返回的结果

常见面试题

1. 两数之和

给定一个整数数组(无重复元素)和一个目标值，找出数组中和为目标值的两个数

1. 按照从小到大的顺序输出结果对
2. 可以假设每个输入只对应一种答案

Input: numbers={2, 7, 11, 15}, target=9
Output: {2, 7}

暴力解决

1. 遍历取一个数，然后再遍历i+1 取2个数之和
2. 时间复杂度： O(n^2)

正确解法 （排序+双指针）

1. 我们先对数组进行排序
2. 一个指针（start指针）指向数组的第一个元素（也是最小元素），另一个指针（end指针）指向数组的最后一个元素（最大的）
3. 如果现在2个指针之和大于目标值，说明现在两数之和过大，应使end指针指向更小的数，即索引减小（end—），反之则表明现在两数过小，应使start指针指向更大的数，即索引增加（start++）

public static int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    int start = 0, end = nums.length - 1;
    // 1. 对数组进行排序
    Arrays.sort(nums);
    while (start < end) {
        if (nums[start] + nums[end] == target) {
            result[0] = nums[start];
            result[1] = nums[end];
            break;
        }
        // 小于目标值，前指针后移
        if (nums[start] + nums[end] < target) {
            start++;
        }
        // 大于目标值，后指针前移
        if (nums[start] + nums[end] > target) {
            end--;
        }
    }
    return result;
}

时间复杂度 O(nlogn)

排序：O(nlogn)，两根指针算法O(n)

O(nlogn) + O(n) = O(nlogn)

2. 三数之和

给定一个包含n个整数的数组（无重复元素）nums和一个目标值target，找出数组中和为目标值的三个数

input： nums = [-1, 0, 1, 2, 4],  target = 0    
output: [-1, 0, 1]    

解法（排序+三指针）

1. 首先对数组进行排序
2. 先固定一个数字，看看另外两数之和是否能满足target –num1，这就转化为两数之和的问题

public static int[] threeSum(int[] nums, int target) {
    int[] result = new int[3];
    if (nums.length < 3) {
        return nums;
    }
    Arrays.sort(nums);
    // 第三个指针
    int second = nums.length - 1;
    // 遍历数组
    for (int i = 0; i < nums.length - 2; i++) {
        // 第二个指针
        int first = i + 1;
        while (first < second) {
            if (nums[first] + nums[second] == target - nums[i]) {
                result[0] = nums[i];
                result[1] = nums[first];
                result[2] = nums[second];
                return result;
            }
            if (nums[second] + nums[first] < target - nums[i]) {
                first++;
            }
            if (nums[second] + nums[first] > target - nums[i]) {
                second--;
            }
        }
    }
    return result;
}

时间复杂度（O(n^2）

1. 排序： nlogn 遍历n个数，进行2数之和（n*O(n)）

   O(nlogn)+n*O(n) = O(n^2)

3. 反转数组

给定一个数组，反转数组中所有的数字

Input: {1,2,3,45,6,7}
output: {7,6,45,3,2,1}

解法（双指针）

1. 定义2个指针在开始位置和结束位置（start ,end)
2. 然后交互2个地方的位置

public static void swap(int start, int end, int[] nums) {
    int temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
}

public static int[] reserveArray(int[] nums) {
    int start = 0, end = nums.length - 1;
    while (start < end) {
        // 交换完成更新索引
        swap(start++, end--, nums);
    }
    return nums;
}

时间复杂度 O(n)

4. 奇数偶数排序

给定一组整数，对它们进行排序，以便所有的奇数整数在偶数整数之前出现，元素的顺序可以改变。排序的奇数和偶数的顺序无关紧要

解法（双指针）

1. 取2个指针（开始位置start，结束位置end）
2. 如果start的指针为偶数，end指针为奇数，就交换2个位置，如果start指针为偶数，但是end指针也是偶数，那就需要把end指针前移，直到不是偶数为止，如果start指针的数为奇数，就后移指针，直到不是奇数为止。

public static int[] oddEvenSort(int[] nums) {
    int start = 0, end = nums.length - 1;
    while (start < end) {
        // start 为奇数, 就偏移指针只到为偶数
        while (start < end && nums[start] % 2 != 0) {
            start++;
        }
        // end 为偶数
        while (start < end && nums[end] % 2 == 0) {
            end--;
        }
        if(start < end ) {
            swap(start++, end--, nums);
        }
    }
    return nums;
}

public static void swap(int start, int end, int[] nums) {
    int temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
}

易错点

1. 外部的start < end的时候，内部也需要判定最基本的条件while (start < end && nums[start] % 2 != 0)

5. 合并两个有序数组

给定两个有序整数数组num1和num2 , 请按照递增顺序将他们合并到一个排序数组中

intput:  {1,3, 5} {2,4,6}
output: {1,2,3,4,5,6}

解法（双指针+同方向）

1. 定义2个指针，从2的最左边开始遍历，遍历到2个数组的最右边（最小的）
2. 没有遍历完成的数组进行填充数据

public static int[] merge(int[] num1, int[] num2) {
    int[] result = new int[num1.length + num2.length];
    int index = 0, index1 = 0, index2 = 0;
    // 判定index1 index2必须要在num1 和 num2
    while (index1 < num1.length && index2 < num2.length) {
        if (num1[index1] < num2[index2]) {
            result[index++] = num1[index1++];
        } else {
            result[index++] = num2[index2++];
        }
    }
    for (int i = index1; i < num1.length; i++) {
        result[index++] = num1[i];
    }
    for (int i = index2; i < num2.length; i++) {
        result[index++] = num2[i];
    }
    return result;
}