三数之和
15：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
class Solution {public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new LinkedList<>();if(nums==null||nums.length<3)return result; Arrays.sort(nums);for(int i=0;i<nums.length-2;i++){//找第一个数字if(i>0&&nums[i]==nums[i-1])continue;int first = nums[i];int target = -nums[i];int left = i+1;int right = nums.length -1; while(left<right){if(nums[left]+nums[right]==target){result.add(Arrays.asList(new Integer[]{first,nums[left],nums[right]}));left++;right--;while(nums[left]==nums[left-1]&&left<right)left++;while(nums[right]==nums[right+1]&&left<right)right--;}else if(nums[left]+nums[right]<target)left++;elseright--;}}return result;}
}搜索旋转排序数组
33：整数数组 nums 按升序排列，数组中的值互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
class Solution {public int search(int[] nums, int target) {int low = 0;int high = nums.length-1;while(low<=high){int mid = (low+high)/2;if(nums[mid]==target)return mid;//mid右边是有序的if(nums[mid]<nums[high]){//在mid右边区间if(nums[mid]<target&&nums[high]>=target){low =mid+1;}else{high = mid -1;} }else{//mid左边有序//在mid左边区间if(nums[mid]>target&&nums[low]<=target){high =mid-1;}else{low = mid+1;} }}return -1;}
}class Solution {public int search(int[] nums, int target) {int low = 0;int high = nums.length-1;while(low<=high){int mid = (low+high)/2;if(nums[mid]==target){return mid;}// 左边有序，此时要有等于号，因为取下界，mid和low会重合if(nums[low]<=nums[mid]){if(nums[low]<=target&&nums[mid]>target){high = mid -1;}else{low = mid+1;} }else{if(nums[mid+1]<=target&&nums[high]>=target){low = mid + 1;}else{high = mid -1;} }}return -1;}
}旋转数组的最小数字
牛客必刷100 BM22：有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
public class Solution {public int minNumberInRotateArray(int [] array) {if(array.length==0){return 0;}int left = 0;int right = array.length-1;while(left<=right){int mid = (left+right)/2;if(array[mid]>array[right]){left = mid+1;}else if(array[mid]<array[right]){right = mid;}else{right--;}}return array[left];}
在排序数组中查找元素的第一个和最后一个位置
34：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
class Solution {public int[] searchRange(int[] nums, int target) {int firstIndex = searchFirst(nums,target);int lastIndex = searchLast(nums,target);return new int[]{firstIndex,lastIndex};}public int searchFirst(int[] nums,int target){int left=0,right=nums.length-1;while(left<=right){int mid = left + (right - left)/2;if(nums[mid]==target){if(mid==0||nums[mid-1]!=nums[mid]){return mid; }else{right = mid-1;}}else if(nums[mid]<target){left = mid +1;}else{right = mid-1;}}return -1;}public int searchLast(int[] nums,int target){int left=0,right=nums.length-1;while(left<=right){int mid = left + (right - left)/2;if(nums[mid]==target){if(mid==nums.length-1||nums[mid+1]!=nums[mid]){return mid;}else{left = mid+1;}}else if(nums[mid]<target){left = mid +1;}else{right = mid-1;}}return -1;}
}排序数组中元素个数
剑指offer53：统计一个数字在排序数组中出现的次数。
class Solution {public int search(int[] nums, int target) {return findFirst(nums,target+1) - findFirst(nums,target);}public int findFirst(int[] nums, int k){int left = 0, right = nums.length-1;while(left<=right){int mid = left + (right - left)/2;if(nums[mid] == k){right = mid-1;}else if(nums[mid]<k){left = mid +1;}else{right = mid-1;}}return right;}
}下一个排列
31：实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须 原地 修改，只允许使用额外常数空间。
class Solution {public void nextPermutation(int[] nums) {int length = nums.length;for(int i=length-1;i>=1;i--){//从后往前找到第一个相邻的升序对,此时nums[i,end)是降序的,nums[i]>nums[i-1]//这一步相当于到哪一位需要进位if(nums[i]>nums[i-1]){//nums[i,end)中 从后往前找到第一个大于nums[i-1]的数，即找到后面降序区间中最接近nums[i-1]且大于nums[i-1]的数字nums[j]//这一步相当于进位到哪个数for(int j=length-1;j>=i;j--){//nums[j]与nums[i-1]交换,此时nums[i,end)还是降序，转为升序//这一步相当于进位之后，恢复后面数字的顺序if(nums[j]>nums[i-1]){int temp = nums[i-1];nums[i-1] = nums[j];nums[j]=temp;Arrays.sort(nums,i,length);return ;}}}}Arrays.sort(nums);return;}
}无序数组中找到左侧比他小右侧比他大的数
遍历两次数组，第一次把左边都小于当前的位置记录下来，第二次把右边都小于自己的位置记录下来，最后统计两次都满足条件的位置，即 mos[ i ] = 2
public void findMiddle(int[] nums,int[] mos){int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for(int i=0;i<nums.length;i++){if(nums[i]>=max){max = nums[i];mos[i]++;}}for(int i =nums.length-1;i>=0;i--){if(nums[i]<=min){min = nums[i];mos[i]++;}}}合唱队
N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。
public class Main {public int minOpts(int[] array){int length = array.length;int[] left = new int[length];int[] right = new int[length];left[0]=1;right[length-1]=1;int ans = Integer.MIN_VALUE;// 左边的最长递增子序列for(int i=1;i<length;i++){left[i] = 1;for(int j=0;j<i;j++){if(array[j]<array[i]){left[i] = Math.max(left[i],left[j]+1);}}}// 右边的最长递增子序列for(int i=length-2;i>=0;i--){right[i] = 1;for(int j=length-1;j>i;j--){if(array[j]<array[i]){right[i] = Math.max(right[i],right[j]+1);}}}for(int i=0;i<length;i++){ans = Math.max(left[i]+right[i]-1,ans);}return length-ans;}}缺失的第一个正数
41：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
class Solution {public int firstMissingPositive(int[] nums) {for(int i=0;i<nums.length;i++){while(nums[i]>0&&nums[i]<=nums.length&&nums[i]!=nums[nums[i]-1]){swap(nums,i,nums[i]-1);}}for(int i=0;i<nums.length;i++){if(nums[i]!=i+1)return i+1;}return nums.length+1;}public void swap(int[] nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}寻找峰值
162：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
class Solution {public int findPeakElement(int[] nums) {int low = 0;int high = nums.length-1;while(low<high){int mid =(low+high)/2;if(nums[mid]>nums[mid+1]){high = mid;}else{low = mid+1;}}return low;}
}寻找两个正序数组的中位数
4：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 = nums1.length;int length2 = nums2.length;int length = length1+length2;if(length%2==1){return kthElement(nums1,nums2,length/2+1);}else{return (kthElement(nums1,nums2,length/2)+kthElement(nums1,nums2,length/2+1))/2.0;}}public int kthElement(int[] nums1,int[] nums2,int k){int index1=0;int index2=0;while(true){if(index1==nums1.length){return nums2[index2+k-1];}if(index2==nums2.length){return nums1[index1+k-1];}if(k==1){return Math.min(nums1[index1],nums2[index2]);}int newindex1 = Math.min(nums1.length-1,index1+k/2-1);int newindex2 = Math.min(nums2.length-1,index2+k/2-1);int pivot1 = nums1[newindex1];int pivot2 = nums2[newindex2];if(pivot1<pivot2){k-= newindex1-index1+1;index1 = newindex1+1;}else{k-= newindex2-index2+1;index2 = newindex2+1;}}}
}搜索二维矩阵II
240：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int x=0,y=n-1;//从右上角或者左下角都可以while(x<m&&y>=0){if(matrix[x][y]==target){return true;}else if(matrix[x][y]>target){y--;}else{x++;}}return false;}
}数组中的逆序对
剑指 offer51 数组中的逆序对：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
class Solution {int[] temp;int ans = 0;public int reversePairs(int[] nums) {temp = new int[nums.length];merge(nums,0,nums.length-1);return ans;}public void merge(int[] nums,int left,int right){if(left>=right){return ;}int mid = (left+right)/2;merge(nums,left,mid);merge(nums,mid+1,right);mergeSort(nums,left,mid,right);}public void mergeSort(int[] nums,int left,int mid,int right){int i=left,j=mid+1,k=0;while(i<=mid&&j<=right){if(nums[i]<=nums[j]){temp[k++]=nums[i++];}else{temp[k++]=nums[j++];ans += mid-i+1;}}while(i<=mid)temp[k++]=nums[i++];while(j<=right)temp[k++]=nums[j++];for(i=0;i<k;i++){nums[left+i]=temp[i];}}
}数组的最小偏移量
1675：给你一个由 n 个正整数组成的数组 nums 。你可以对数组的任意元素执行任意次数的两类操作：如果元素是 偶数 ，除以 2。例如，如果数组是 [1,2,3,4] ，那么你可以对最后一个元素执行此操作，使其变成 [1,2,3,2]。如果元素是 奇数 ，乘上 2。例如，如果数组是 [1,2,3,4] ，那么你可以对第一个元素执行此操作，使其变成 [2,2,3,4]。数组的 偏移量是数组中任意两个元素之间的 最大差值 。返回数组在执行某些操作之后可以拥有的 最小偏移量 。
class Solution {public int minimumDeviation(int[] nums) {TreeSet<Integer> set = new TreeSet<>();// 使每个元素达到最大值for(int i=0;i<nums.length;i++){if(nums[i]%2==1){set.add(nums[i]*2);}else{set.add(nums[i]);}}int ans = set.last()-set.first();// 若最大值为偶数，则降低最大值，计算当前的偏移差while(set.last()%2==0){int last = set.last();set.remove(last);set.add(last/2);ans = Math.min(set.last()-set.first(),ans);}return ans;}
}两个分数之和为1的数量
微软笔试：给定两个数组，X[i]是第i个数的分子，Y[i]是第i个数的分母。找出两个分数之和为1的组合数。
public int solution(int[] X,int[] Y){int length = X.length;int ans = 0;HashMap<String, Integer> map = new HashMap<>();for(int i=0;i<length;i++){int GCD = gcd(X[i],Y[i]);X[i]/=GCD;Y[i]/=GCD;String target = ""+(Y[i]-X[i])+Y[i];if(map.containsKey(target))ans += map.get(target);String curNum = ""+X[i]+Y[i];map.put(curNum,map.getOrDefault(curNum,0)+1);}return ans;
}
public int gcd(int a, int b){return a==0?b:gcd(b%a,a);
}寻找重复数
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
class Solution {public int findDuplicate(int[] nums) {int slow = 0, fast = 0;slow = nums[slow];fast = nums[nums[fast]];while(slow!=fast){slow = nums[slow];fast = nums[nums[fast]];}int p = 0, q = slow;while(p!=q){p = nums[p];q = nums[q];}return p;}
}