数组中的问题其实最常见
如：排序（选择排序、插入排序、归并排序、快速排序）、查找（二分查找法）、数据结构（栈、队列、堆）
注意：
1、如果没有解，返回什么？
2、如果有多个解，返回哪个解？若要返回任意解，顺序有要求吗？
3、字符串相关：空串如何看、大小写问题、字符的取值范围
ps：例题选自LeetCode
一、从二分查找法看如何写出正确的程序
思想：保证循环的循环不变量
明确变量的含义
整型溢出解决方法：由(l+r)/2 修改为l+(r-l)/2
二、移动、移除数组中特定元素
算法思想：遍历一遍数组，将遍历到的不为0的元素，移到数组前方标记位置。
时间复杂度O(n)，空间复杂度O(1)。
题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
public class MoveZeros<Item> {
public static int[] moveZeroes(int[] nums) {
/**
* 1、创建一个新的数组 newNums
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：40 MB, 在所有 Java 提交中击败了5.62% 的用户
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
int[] newNums = new int[nums.length];
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0){
newNums[j] = nums[i];
j++;
}
}
for (int i = j; i < nums.length; i++) {
newNums[i] = 0;
}
return newNums;
/**
* 2、最优解——交换位置，发现不为0元素，移到前方，注意全为非0时k与i。
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：39.6 MB, 在所有 Java 提交中击败了5.62% 的用户
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
int k = 0; // 记录当前不为0的位置 ☆
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0 ){
if (k != i){ // 如果k==i，则只需要使k+1即可。
nums[k] = nums[i];
nums[i] = 0; // 交换操作，这里为了简单直接令为0了。
}
k++;
}
}
return nums;
/**
* 3、遍历当前位置之后的元素，不为0则移到当前位置。——比较复杂
* 执行用时：5 ms, 在所有 Java 提交中击败了5.00% 的用户
* 内存消耗：40 MB, 在所有 Java 提交中击败了5.62% 的用户
* 时间复杂度：O(n^2)
* 空间复杂度：O(1)
*/
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0 && i < nums.length-1) {
int j = i+1;
while (nums[j] == 0 && j < nums.length-1){
j++;
}
if (j < nums.length && nums[j] !=0) {
nums[i] = nums[j];
nums[j] = 0;
}
}
}
return nums;
}
public static void main(String[] args) {
int[] m = {1,4,6,0,2,6,0,0,7};
for (int i = 0; i < moveZeroes(m).length; i++) {
System.out.println(moveZeroes(m)[i]);
}
}
}
题目：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
要求：
1、不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
2、元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 :
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素是什么。
- 算法思想同上题283中方法二一样。
/** 删除数组中值为val的元素，并返回该数组。
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：38.4 MB, 在所有 Java 提交中击败了5.68% 的用户
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
public int removeElement(int[] nums, int val) {
int k = 0; // 数组中前k个元素不为val
int tem = 0; // 交换位置中间变量
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val ){
if (i != k){
tem = nums[k];
nums[k] = nums[i];
nums[i] = tem;
}
k++;
}
}
return k;
}
题目：给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
要求：不要使用额外的数组空间，你必须在 原地 修改输入数组，并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
算法思想：遍历一遍数组，记录遍历到的上一元素值X标记其位置，对比当前元素，若不相等，则将该元素移到数组前方标记位置。更新X及标记的位置。
// 执行用时：1 ms, 在所有 Java 提交中击败了98.16% 的用户
// 内存消耗：40.3 MB, 在所有 Java 提交中击败了96.86% 的用户
public int removeDuplicates(int[] nums) {
int lastNumber = 0; // 记录当前无重复值的位置
for(int i = 0;i < nums.length;i++){
if(nums[i] != nums[lastNumber]){
lastNumber ++; // 发现新元素，位置加一
nums[lastNumber] = nums[i]; // 赋值
}
}
return lastNumber+1;
}
- 在c++中，可以使用 freq[256] 来判断元素出现频率。
题目：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组**并在使用 O(1) 额外空间的条件下完成。
算法思想：遍历一遍数组，记录遍历到的上一元素值X标记其位置，记录出现次数。对比当前元素，若相等，判断出现次数time，小于等于2次，或不相等。则将该元素移到数组前方标记位置，更新X及标记的位置。
// 执行用时：1 ms, 在所有 Java 提交中击败了97.38% 的用户
// 内存消耗：38.8 MB, 在所有 Java 提交中击败了80.16% 的用户
public int removeDuplicates(int[] nums) {
int lastNumber = 0; // 上一个元素位置，从第一个开始。
int time = 1; // 元素出现次数，第一个元素已有，所以初始是1次
for(int i = 1;i < nums.length; i++){ // i 从第二个开始
if(nums[i] == nums[lastNumber]){
time++;
if(time <= 2){
lastNumber++;
nums[lastNumber] = nums[i];
}
}else{
lastNumber++;
nums[lastNumber] = nums[i];
time = 1;
}
}
return lastNumber + 1;
}
三、计数排序、归并排序
题目：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶： 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
算法思想：三路快排（最优）
1、遍历出0、1、2的个数，依次给数组赋值
/**
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：38.1 MB, 在所有 Java 提交中击败了6.67% 的用户
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
int[] count = new int[3];
for (int i = 0; i < nums.length; i++) {
if (nums[i]>=0 && nums[i]<3){
count[nums[i]]++; // count中下标对应值加1
}
}
// 按照count中的统计结果，给nums数组赋值。
int k = 0;
for (int i = 0; i < 3;i++){
for (int j = 0; j < count[i]; j++,k++) {
nums[k]=i;
}
}
2、三路快排
/**
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：38.2 MB, 在所有 Java 提交中击败了6.67% 的用户
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
int zero = -1;
int two = nums.length;
for (int i = 0;i<two;){
if (nums[i] == 0){
zero++;
nums[zero] = nums[i];
if(zero != i){
nums[i] = 1;
}
i++;
}else if (nums[i] == 1){
i++;
}else if (nums[i] == 2){
two--;
nums[i] = nums[two];
nums[two] = 2;
}else {
System.out.println("请输入只有0、1、2的数字！");
return;
}
}
题目：
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
算法思想：从后往前排——不借用辅助空间，在nums1上交换元素实现。
（1）一次归并排序——借用一个辅助数组，从前往后排
public static void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 执行用时：14 ms, 在所有 Java 提交中击败了5.29% 的用户
* 内存消耗：39.9 MB, 在所有 Java 提交中击败了5.06% 的用户
* 时间复杂度：O(n+m) 空间复杂度：O(n)
*/
int[] p = new int[nums1.length]; // 存储最终结果的辅助数组
int a = 0;
int b = 0;
for (int i = 0; i < m+n; i++){
if(a == m){
p[i] = nums2[b];
b++;
}else if(b == n){
p[i] = nums1[a];
a++;
}else if (a < m || b<n){
if (nums1[a] <= nums2[b]){
p[i] = nums1[a];
a++;
}else if(nums1[a]>nums2[b]){
p[i] = nums2[b];
b++;
}
}
}
for (int i = 0;i<nums1.length;i++){
nums1[i] = p[i];
System.out.println(nums1[i]);
}
}
（2）从后往前排——不借用辅助空间，在nums1上交换元素实现。
☆☆☆☆☆☆最优☆☆☆☆☆☆
public static void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
* 内存消耗：40 MB, 在所有 Java 提交中击败了5.06% 的用户
* 时间复杂度：O(m+n) 空间复杂度O(1)
*/
int c = m-1;
int d = n-1;
for (int i = m + n - 1; i >= 0; i--) {
if(c==-1){
nums1[i] = nums2[d];
d--;
}else if(d==-1){
nums1[i] = nums1[c];
c--;
}else {
if (nums1[c]>nums2[d] ){
nums1[i] = nums1[c];
c--;
}else if(nums1[c] <= nums2[d]){
nums1[i] = nums2[d];
d--;
}
}
}
（3）用排序函数排序，忽略了数组有序的条件。
public static void merge(int[] nums1, int m, int[] nums2, int n) {
/**
* 执行用时：1 ms, 在所有 Java 提交中击败了23.72% 的用户
* 内存消耗：39.8 MB, 在所有 Java 提交中击败了5.06% 的用户
*/
System.arraycopy(nums2, 0, nums1, m, n);
Arrays.sort(nums1);
}
题目：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
算法思想：先排序（堆排序、快排 O(nlogn)），在找到第K大的元素。
四、对撞指针——寻找两数和、回文串、字符串倒序、元素翻转——双索引技术
题目：给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
算法思路：设置左右两个指针，如果相加大于目标值，右指针前进一位；如果相加小于目标值，左指针前进一位。（不会错过目标值）
思路2：双重循环暴力破解，思路简单，效率不高。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] a = new int[2];
for(int i = 0,j=numbers.length -1 ;i < numbers.length && j > i ; ){
if(numbers[i] + numbers[j] == target){
a[0] = i+1;
a[1] = j+1;
break;
}
else if(numbers[i] + numbers[j] > target){
j--;
}else if(numbers[i] + numbers[j] < target){
i++;
}
}
// 思路二，双重循环
// for(int i=0;i<numbers.length;i++){
// for(int j = numbers.length-1;j>i;j--){
// if (numbers[i]+numbers[j]==target){
// a[0] = i+1;
// a[1] = j+1;
// }else if(numbers[i]+numbers[j]<target){
// break;
// }
// }
// }
return a;
}
}
题目：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
算法思路：使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood\textit{sgood}sgood 就是回文串。
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sgood = new StringBuffer();
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isLetterOrDigit(ch)) {
sgood.append(Character.toLowerCase(ch));
}
}
StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
return sgood.toString().equals(sgood_rev.toString());
}
}
使用双指针。初始时，左右指针分别指向 sgood 的两侧，随后我们不断地将这两个指针相向移动，每次移动一步，判断这两个指针指向的字符是否相同。遇到其他字符前进一位，当这两个指针相遇时，就说明 sgood 是回文串。
class Solution {
public boolean isPalindrome(String s) {
StringBuffer sgood = new StringBuffer();
int length = s.length();
for (int i = 0; i < length; i++) {
char ch = s.charAt(i);
if (Character.isLetterOrDigit(ch)) {
sgood.append(Character.toLowerCase(ch));
}
}
int n = sgood.length();
int left = 0, right = n - 1;
while (left < right) {
if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
return false;
}
++left;
--right;
}
return true;
}
}
思路同上，首尾设置两个指针，遇到其他字符前进一位，两指针遇到不相同的字符，就返回false，直到两指针相遇跳出循环返回true。judjeChar() 函数可用isLetterOrDigit() 代替，不用自己写。
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
// byte[] array = new byte[s.getBytes().length];
int i = 0,j = 0,m = 0;
if(s.length() > 0){
j = s.length() - 1;
m = (s.length())/2;
}else{
return true;
}
while(i<j){
if(!(judjeChar(s.charAt(i)))){
i++;
}
if(!(judjeChar(s.charAt(j)))){
j--;
}
System.out.println("i="+i+"值是"+s.charAt(i)+" "+"j="+j+"值是"+s.charAt(j));
if(judjeChar(s.charAt(i)) && judjeChar(s.charAt(j))){
if(!(s.charAt(i) == (int)s.charAt(j))){
return false;
}
i++;
j--;
}
}
return true;
}
public boolean judjeChar(char ch){
// 判断字符是否是英文或数字，不是反回 false 否则反回 true
int num = (int) ch;
if(num <= 122 && num >= 97){
return true;
}else if(num >= 48 && num <= 57){
return true;
}else {
return false;
}
}
}
题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
算法思想：设置左右两个指针，分别交换两指针所指向的值，再向前移动。
public void reverseString(char[] s) {
char one;
int i = 0;
int j = 0;
if(s.length > 0){
j = s.length - 1;
}
while(i<j){
one = s[i];
s[i] = s[j];
s[j] = one;
i++;
j--;
}
}
题目：编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1：
输入："hello"
输出："holle"
算法思想：设置左右两个指针，判断不是元音字母，则向前进一位，直至两指针均指向元音字母，交换两指针的值。重复上述过程，至两指针相遇。
class Solution {
public String reverseVowels(String s) {
char[] str = s.toCharArray();
for(int i = 0;i<str.length;i++){
System.out.println(str[i]);
}
char ch;
int i=0,j=0;
if(s.length()>0){
j = s.length() - 1;
}else{
return "";
}
while(i<j){
if(!yuanyin(s.charAt(i))){
i++;
}
if(!yuanyin(s.charAt(j))){
j--;
}
if(yuanyin(s.charAt(i)) && yuanyin(s.charAt(j))){
ch = str[i];
str[i] = str[j];
str[j] = ch;
i++;
j--;
}
}
return new String(str);
}
public boolean yuanyin(char c){
if (c == 'a' || c == 'e' || c == 'i'|| c == 'o'|| c == 'u'||c == 'A' || c == 'E' || c == 'I'|| c == 'O'|| c == 'U'){
return true;
}else{
return false;
}
}
}
题目：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
算法思想：设置左右两个指针从数组两端开始遍历，先算出当前最大面积。再比较两指针指向的值，较小的一方，前进一位，再算出当前最大面积
方法二：双重循环，暴力破解。
public int maxArea(int[] height) {
int left = 0,right = height.length - 1;
int maxArea = 0;
while(left<right){
maxArea = Math.max(Math.min(height[left],height[right]) * (right - left) , maxArea);
if(height[left] <= height[right]){
left ++;
}else if(height[left] > height[right]){
right --;
}
}
return maxArea;
}
五、滑动窗口——双索引
- 长度最小的子数组 (209)——facebook面试题
题目：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
算法思想：滑动窗口。如果从i到j的和sum<s，j++；扩大窗口范围，直到sum>s；再让i++；尝试缩小窗口范围，找到最小的length。直到j>nums.length结束。
方法二：暴力解法，遍历所有连续子数组，计算其和sum，验证sum>=s是否成立。O(n^3)
方法三：优化暴力解法：O(n^2)【不用每次都算sum，找到快速判断的方法】
- 什么叫子数组？连续子数组？
nums = [2,3,1,2,4,3]
子数组 num1=[1,3]
连续子数组 num2=[1,2,4]
public int minSubArrayLen(int s, int[] nums) {
int i = 0,j = 0;
int sumLength = 0;
int minSumLength = 0;
boolean first = true;
if(nums.length == 0){
return 0;
}
while(j <= nums.length){
int nowSum = 0;
for(int a =i;a<=j;a++){
nowSum = nowSum + nums[a];
}
if(j == nums.length-1 && nowSum < s){
return minSumLength;
}
if(nowSum < s){
j++;
}
if(nowSum >= s){
sumLength = j-i+1;
if(first){
first = false;
minSumLength = sumLength;
}else{
minSumLength = Math.min(sumLength,minSumLength);
}
i++;
}
}
return minSumLength;
}
- 官方答案，思路一样，代码更简练，时间更快。（两个while）
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = Math.min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
// 如果没有ans（ans = 初始值Integer.MAX_VALUE），返回0，否则返回ans。
return ans == Integer.MAX_VALUE ? 0 : ans;
}
(438)——要plus
最小覆盖子串 (76)——太难了，直接看解析吧。
题目：给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入：S = "ADOBECODEBANC", T = "ABC"
输出："BANC"
提示：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
算法思想：滑动窗口，如何判断子字符串是否包含字符串T是关键。**
