6.数组（六）

https://leetcode-cn.com/tag/array/

题目汇总

153. 寻找旋转排序数组中的最小值中等

154. 寻找旋转排序数组中的最小值 II困难

162. 寻找峰值中等

167. 两数之和 II - 输入有序数组简单

169. 多数元素简单，与剑指Offer一样

189. 旋转数组简单

209. 长度最小的子数组中等

216. 组合总和 III中等

217. 存在重复元素简单

153. 寻找旋转排序数组中的最小值中等，与剑指Offer一样

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2]，输出: 1
示例 2:
输入: [4,5,6,7,0,1,2]，输出: 0

思路：二分查找

每次进入无序的那部分找出最小值

class Solution {
    public int findMin(int[] nums) {//执行用时 :0 ms
        if(nums == null || nums.length <= 0)
            return 0;
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            if(nums[left] < nums[right])
                return nums[left];
            int mid = (right - left) / 2 + left;
            if(nums[mid] > nums[right]){//从left到mid时递增的，最小值一定在mid到right之间
                left = mid + 1;
            }else if(nums[mid] < nums[right]){//从mid到right是递增的，最小值一定left到mid之间，包括mid
                right = mid;
            }else{//其他情况
                left++;
            }
        }
    return nums[left];
    }
}

154. 寻找旋转排序数组中的最小值 II困难

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5]，输出: 1
示例 2：
输入: [2,2,2,0,1]，输出: 0

思路：二分查找

与上题类似，区别在于数组中可能存在重复的元素，当nums[mid] = nums[right]时，应该将 right 减 1 防止重复数字是最小元素。

class Solution {
    public int findMin(int[] nums) {//执行用时 :0 ms
        int left = 0;
        int right = nums.length - 1;  
        while(left < right){
            if(nums[left] < nums[right])
                return nums[left];
            int mid = (right - left)/2 + left;
            if(nums[mid] > nums[right]){
                left = mid + 1;
            }else if(nums[mid] < nums[right]){
                right = mid;
            }else{
                right--;
            }
        }
    return nums[left];
    }
}

162. 寻找峰值中等

峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。
示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。
说明:你的解法应该是 O(logN)时间复杂度的。

思路一：

因为两个相邻的元素不相等，遍历数组，如果当前元素的值大于下一个元素的值，那么这个元素一定是峰值
如果元素递增，一直遍历到最后一个元素即为峰值。

class Solution {
    public int findPeakElement(int[] nums) {//执行用时 :0 ms
        for(int i=0;i<nums.length-1;i++){
            if(nums[i] > nums[i+1])
            return i;
        }
    return nums.length - 1;
    }
}

思路二：二分查找

class Solution {
    public int findPeakElement(int[] nums) {//执行用时 :0 ms
        if(nums == null || nums.length <= 0)
            return 0;
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] > nums[mid + 1]){// mid比右侧大, 峰顶在左侧或就在mid处
                right = mid;//[left,mid]
            }else{
                left = mid + 1;//mid比右侧小,峰顶在右侧[mid+1,right]
            }
        }
    return left;
    }
}

167. 两数之和 II - 输入有序数组简单

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值index1 和 index2，其中 index1 必须小于 index2。
说明:返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2

思路：双指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {//执行用时 :1 ms
        int[] result = new int[2];
        if(numbers == null || numbers.length <= 1)
            return result;
        int left = 0;
        int right = numbers.length-1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                result[0] = left + 1;//下标是从1开始的，要加1
                result[1] = right + 1;
                return result;
            }else if(sum < target){
                left++;
            }else{
                right--;
            }
        }
    return result;
    }
}

169. 多数元素简单，与剑指Offer一样

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

思路：

数组中有一个数字出现的次数超过数组长度的一半，那么其他数字出现的次数总和一定比这个数字出现的次数要小。遍历数组的时候保存两个值，一个是数组中的一个数字，另一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；不同则减一。如果次数为0，则保存下一个数字，并把次数设为1。遍历结束后，所保存的数字即为所求，然后再判断它是否符合条件。
时间复杂度为O(n)

class Solution {
    public int majorityElement(int[] nums) {//执行用时 :1 ms
        if(nums.length <= 0)
            return 0;
        int result = nums[0];
        int count = 1;//
        // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        for(int i=1;i<nums.length;i++){
            if(nums[i]==result)
                count++;
            else{
                count--;
                if(count==0){
                    // 更新result的值为当前元素，并把次数设为1
                    result = nums[i];
                    count = 1;
                }
            }
        }
        // 判断result是否符合条件，即出现次数大于数组长度的一半
        int times = 1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]==result){
                times++;
            }
        }
        if(times<=nums.length/2){
            return 0;
        }
     return result;   
    }
}

189. 旋转数组简单

给定一个数组，将数组中的元素向右移动 k个位置，其中 k是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:向右旋转 1 步: [7,1,2,3,4,5,6]，向右旋转 2 步: [6,7,1,2,3,4,5]， 向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 向右旋转 1 步: [99,-1,-100,3]，向右旋转 2 步: [3,99,-1,-100]
说明:尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的 原地算法。

思路一：使用额外的数组

定义一个新的数组，把原数组里下标为 i 的元素放在新数组 (i+k)%数组长度的位置，然后把新的数组拷贝到原数组中。
时间复杂度为 O(n)，空间复杂度为O(n)，不符合要求。

class Solution {
    public void rotate(int[] nums, int k) {//执行用时 :1 ms
        int[] a = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            a[(i + k) % nums.length] = nums[i];
        }
        for(int i=0;i<nums.length;i++){
            nums[i] = a[i];
        }

    }
}

思路二：翻转

将数组中的元素向右移动 k个位置相当于将 k%n 个尾部元素移动到头部，剩下的元素依次向后移动。
分为三步进行，首先将所有元素反转，然后反转前 k 个元素，最后反转后面 n-k 个元素。
时间复杂度为 O(n)，空间复杂度为O(1)。

class Solution {
    public void rotate(int[] nums, int k) {//执行用时 :0 ms
        k %= nums.length;
        reverse(nums, 0, nums.length-1);//首先将所有元素反转
        reverse(nums, 0, k-1);//然后反转前 k 个元素
        reverse(nums, k, nums.length-1);//再反转后面 n-k 个元素
    }
    private void reverse(int[] nums, int start, int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

209. 长度最小的子数组中等

给定一个含有 n个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法

思路：双指针

设置两个指针表示一个滑动窗口，窗口中的元素小于目标值，右指针向右移，扩大窗口。窗口中的元素大于目标值，比较当前窗口大小是否为最小值，左指针向右移，缩小窗口。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {//执行用时 :2 ms
        if(nums == null || nums.length <= 0)
            return 0;
        int left = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int right=0;right<nums.length;right++){
            sum += nums[right];//扩大区间
            while(sum >= s){
                min = Math.min(min, right - left + 1);
                sum -= nums[left++];//减小区间
            }
        }
    return min == Integer.MAX_VALUE ? 0 : min;
    }
}

216. 组合总和 III中等

找出所有相加之和为 n 的 k个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：所有数字都是正整数。解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

与 39. 组合总和、 40. 组合总和 II类似

思路：回溯法+剪枝

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {//执行用时 :0 ms
        List<List<Integer>> res = new ArrayList<>();
        dfs(1, n, k, new ArrayDeque<>(), res);
        return res;

    }
     /**
     * @param begin      本轮搜索的起点下标
     * @param n          和n
     * @param k          剩下要找 k 个数
     * @param path       从根结点到任意结点的路径
     * @param res        结果集变量
     */
    private void dfs(int begin,int n, int k,Deque<Integer> path,List<List<Integer>> res){
        if(k == 0 && n == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        
        for(int i=begin;i<=9;i++){
            if( n-i < 0 || k <= 0)
                break;
            path.addLast(i);
            dfs(i+1, n-i,k-1,path,res);
            path.removeLast();
        }
    }
}

217. 存在重复元素简单，与剑指Offer一样

给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true</pre>

思路：哈希

利用HashSet存储对象，从头到尾扫描数组中的每个数，如果哈希表里还没有这个数字，就把它加入哈希表；如果哈希表中已经存在该数字，就说明有重复的数字。时间复杂度O(n)

class Solution {
    public boolean containsDuplicate(int[] nums) {//执行用时 :15 ms
        if(nums == null || nums.length <= 1)
            return false;
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                return true;
            }else{
                set.add(nums[i]);
            }
              
        }
    return false;
    }
}