题目1——最长无重复子数组
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同，子数组是连续的。
示例
输入：[1,2,3,1,2,3,2,2]
输出：3(最长子数组为[1,2,3])
输入：[2,2,3,4,8,99,3]
输出：5(最长子数组为[2,3,4,8,99])
解题思路
使用两个指针i和j，i不断后移遍历数组，把扫描过的元素放入到map当中，如果当前元素不在map当中，表明元素未重复，就一直往后移，同时记录不重复元素子数组的长度Math.max(max_len,i-j+1)；如果当前元素在map当中，则更新j的位置为Math.max(j,map.get(a[i])+1)，因为遇到的重复数字可能在j之前，所以为了确保连续的子数组数字不重复，应该比较两个位置。
代码实现
import java.util.*;
public class Solution {
public int maxLength (int[] arr) {
if(arr.length == 0)
return 0;
if(arr.length == 1)
return 1;
int n = arr.length;
int max_len = 0;
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
//i后移遍历数组
for(int i=0,j=0;i<arr.length;++i){
//如果存在重复元素，则更新j的位置
if(map.containsKey(arr[i])){
j = Math.max(j,map.get(arr[i])+1);
}
//否则数字不重复，加入到map中
map.put(arr[i],i);
max_len = Math.max(max_len,i-j+1); //更新最大长度
}
return max_len;
}
}
题目2——分糖果问题
一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
1.每个孩子不管得分多少，起码分到一个糖果。
2.任意两个相邻孩子之间，得分较多的孩子必须拿多一些糖果。（若相同则无此限制）
给定一个数组arr代表得分数组，请返回最少需要多少糖果。
要求：时间复杂度为O(n)，空间复杂度为O(n)。
示例
输入：[1,1,2]
输出：4(最优分配方案为1,1,2)
解题思路
贪心算法总是做出在当前看来是最好的选择，它并不从整体上最优考虑，通过一系列局部最优的选择来达到问题的整体最优解。
该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
要想糖果数少，如果相邻位置没有增加的情况，大家都分到1；如果相邻位置有增加的情况，将分到的糖果加1即可。具体做法如下：
- 使用一个数组来记录每个孩子分到的糖果，并且全部初始化为1；
- 从左到右遍历，如果右边元素比左边大
arr[i]>arr[i-1]，则糖果数加1，否则保持1不变；
- 从右到左遍历，如果左边比相邻右边大
arr[i]>arr[i+1]，并且左边糖果数更小，则更新左边糖果数为右边糖果数+1，否则保持不变；
- 糖果数组累加求和即可。
代码实现
import java.util.*;
public class Solution {
public int candy (int[] arr) {
int n = arr.length;
if(n<=1)
return n;
int[] candy = new int[n];
for(int i=0;i<n;i++)
candy[i] = 1;
//从左到右遍历，如果右边大于左边元素，则增加一个
for(int i=1;i<n;i++){
if(arr[i]>arr[i-1])
candy[i] = candy[i-1]+1;
}
int res = candy[n-1];
//最后一个元素的相邻元素只有左边，所以从倒数第二个元素开始遍历
//从右到左遍历，如果左边大并且糖果数少
for(int i=n-2;i>=0;i--){
if(arr[i]>arr[i+1] && candy[i]<=candy[i+1])
candy[i] = candy[i+1]+1;
res += candy[i];
}
return res;
}
}
题目3——旋转数组
一个数组A中存有n个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M(M>=0)个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ），最后M个数循环移至最前面的M个位置。如果需要考虑程序移动数据的次数尽量少，要如何设计移动方法？
要求：空间复杂度为O(1)，时间复杂度为O(n)。
示例
输入：6, 2, [1,2,3,4,5,6]
输出：[5,6,1,2,3,4]
解题思路
循环右移相当于从第m个位置开始，左右两部分整体反转，比如1234567右移3位得到5671234，1234为左半部分，567为右半部分。具体做法如下：
- 因为m可能大于n，因此需要对n取余，长度为n的旋转数组相当于没有变化；
- 第一次将整个数组翻转，得到数组的逆序；
- 第二次将左边的m个元素翻转；
- 第三次将右边的n-m个元素翻转。
代码实现
import java.util.*;
public class Solution {
public void swap(int[] nums,int s,int e){
int temp = nums[s];
nums[s] = nums[e];
nums[e] = temp;
}
public void reverse(int[] nums,int start,int end){
while(start<end){
swap(nums,start,end);
start++;
end--;
}
}
public int[] solve (int n, int m, int[] a) {
m = m%n;
reverse(a,0,n-1);
reverse(a,0,m-1);
reverse(a,m,n-1);
return a;
}
}
