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;
}
}
