问题描述：给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。
解析：我们将两个数组分为四个部分leftA、leftB、rightA、rightB，使得L= leftA+leftB的大小等于R= rightA+rightB，若是L中最大值小于R中最小值，则认为我们将根据大小将数据划分成两部分，中位数即为边界值。
public double findMedianSortedArrays(int[] nums1, int[] nums2){
int allNum = nums1.length + nums2.length;
if (nums1.length > nums2.length){
int[] tmp = nums1;
nums1 = nums2;
nums2 = tmp;
}
for (int i = 0 ; i <= nums1.length; i++){
int j = (allNum + 1) / 2 - i;
int leftA = i == 0 ?Integer.MIN_VALUE : nums1[i -1];
int leftB = j == 0 ?Integer.MIN_VALUE : nums2[j - 1];
int rightA = i == nums1.length? Integer.MAX_VALUE : nums1[i];
int rightB = j == nums2.length? Integer.MAX_VALUE : nums2[j];
int left = Math.max(leftA, leftB);
int right = Math.min(rightA, rightB);
if (left > right)continue;
if (allNum % 2 == 1){
return left;
}else{
double res = left + right;
return res / 2;
}
}
return 0;
}问题描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解析：二分查找的思想，关键点在于判断mid与r在不在同一段。1.若是mid值大于r则说明不同段；2.若是mid值小于r则同段；3.相等都有可能。
public int minNumberInRotateArray(int [] arr){//二分
if (arr == null || arr.length == 0)return 0;
int l = 0, r = arr.length - 1;
while (l < r){
int mid = l + ((r - l) >> 1);
if (arr[mid] > arr[r]){//mid与r不同段，r在小段，因此mid以及mid之前的数据都不包含最小数据
l = mid + 1;
}else if (arr[mid] == arr[r]){//出现相等的情况，有可能是同段也有可能是不同段，无法判断（比如2，2，2，1，2，2），最保险的方法就是r逐个移动。
r--;
}else{//mid与r同段，那么最小值一定在mid上或mid之前
r = mid;
}
}
return arr[l];
}解析：二分查找的思想，找到该数字第一次出现的位置与最后一次出现的位置，关键点事等于该数值的时候左(右)指针不动，使得左（右）指针会停在第一个(最后一个)出现的位置。
public int GetNumberOfK(int [] array , int k) {
if (array == null || array.length < 1)return 0;
int l = 0;
int r = array.length - 1;
int[] res = new int[2];
while (l <= r){
int mid = l + ((r - l) >> 1) ;
if (array[mid] >= k)r = mid - 1;
else l = mid + 1;
}
if (l < array.length && array[l]==k)res[0] = l;
else return 0;
l = 0;
r = array.length - 1;
while (l <= r){
int mid = l + ((r - l) >> 1) ;
if (array[mid] <= k)l = mid + 1;
else r = mid - 1;
}
if (r >= 0 && array[r] == k){
res[1] = r;
return res[1] - res[0] +1;
}else{
return 0;
}
}问题描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。
解析：二分查找的思想，关键点在于判断mid在哪一段，然后判断target可能在哪一段，然后进行left、right的移动。
public int search(int[] nums, int target) {
if (nums.length == 0)return -1;
int res = -1;
int left = 0, right = nums.length - 1;
while (left <= right){
int mid = left + ((right - left) >> 1);
if (nums[mid] == target)return mid;
if (nums[0] <= nums[mid]){//因为是升序，所以mid在前半段
//分两种情况
//1.target在前半段
//a.target比mid大：left = mid + 1;
//b.target比mid小：right = mid -1;
//2.target在后半段 left = mid + 1;
if (nums[mid] > target && target >= nums[0]){
right = mid -1;
}else {
left = mid + 1;
}
} else {//mid在后半段
//分两种情况
//1.target在前半段 right = mid - 1;
//2.target在后半段
//a.target比mid大：left = mid + 1;
//b.target比mid小：right = mid -1;
if (nums[mid] < target && target < nums[0]){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return -1;
}题目描述：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。你不能倾斜容器，且 n 的值至少为 2。
解析：两个关键点：1.相同情况下两边越远越好.2.区域面积受限于短边。
因此我们从最远距离开始进行遍历，每次移动的时候抛弃短边。
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right){
if (height[left] <= height[right]){
max = Math.max(max, height[left] * (right - left));
left++;
}else{
max = Math.max(max, height[right] * (right - left));
right--;
}
}
return max;
}题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解析：经典双指针题目，排序树组中一个指针逐个遍历，再选取左右双指针在其后遍历，遍历的准则为，若是三者和小于target，则左指针移动，大于则右指针移动，等于则寻到后两指针都移动进行下一次寻找。
此问题还有变体形式，比如求是否有、最接近的数等，求法大致相同。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++){
if (i > 0 && nums[i] == nums[i - 1])continue;//跳过重复元素
int left = i + 1, right = nums.length - 1;
while (left < right){
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0){
//先用后跳过重复元素再后移一位。
//先用后跳是为了重复元素至少利用一个
//通过循环跳过重复元素，最后指针会停在重复元素的最后一个，这时候跳到下一个元素就可。
list.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1])left++;
while (left < right && nums[right] == nums[right - 1])right--;
left++;
right--;
}
else if (sum < 0){
while (left < right && nums[left] == nums[left + 1])left++;
left++;
}
else{
while (left < right && nums[right] == nums[right - 1])right--;
right--;
}
}
}
return list;
}给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
解析：与上一题的思路大致相同，多了一些剪枝的策略。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (nums.length < 4)return res;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++){
if (i > 0 && nums[i] == nums[i - 1])continue;//去重
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)continue;//若是当前最小的四个元素和逗比target大，也就不用继续寻找了。
if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target)continue;//若是当前最大的四个元素都要比target小，当前次也不会有符合要求的四元素。
for (int j = i + 1; j < nums.length - 2; j++){
if (j > i + 1 && nums[j] == nums[j - 1])continue;
int left = j + 1, right = nums.length - 1;
if (nums[i] + nums[j] + nums[left] + nums[left + 1] > target)break;///与上述相同的剪枝方法
if (nums[i] + nums[j] + nums[right] + nums[right - 1] < target)continue;
while(left < right){
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target){
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
}
if (sum <= target){
do{
left++;
}while(left < right && nums[left] == nums[left - 1]);
}
if (sum >= target){
do{
right--;
}while(left < right && nums[right] == nums[right + 1]);
}
}
}
}
return res;
}题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
解析：使用依次将数组元素加入哈希表，若是哈希表中存在target-num[i]，则说明找到了。
public int[] twoSum1(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < nums.length; i++){
if (map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解析：本题的关键是相对位置不变，使用一个flag记录有多少个奇数被固定下来也就是下一个奇数该替换到达的位置，遍历整个数组每次搜索到一个奇数，就让他逐个交换直至flag指向的位置，然后flag后移一位。
public void reOrderArray(int [] arr) {
if (arr == null)return;
int flag = 0;//记录有多少个奇数被固定下来
for (int i = 0; i < arr.length; i++){
if (arr[i] % 2 == 1){
for (int j = i; j > flag; j--){
swap(arr, j, j - 1);
}
flag++;
}
}
}
public void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}解析：在计算一个长子数组的时候，若其左部分小于零，则其没有存在的意义。因此我们在遍历寻找最大子数组的时候，若是当前子数组的和小于0，则认为该子数组可以直接抛弃继续寻找下一个。
public int FindGreatestSumOfSubArray(int[] arr) {
int res = Integer.MIN_VALUE;
int temp = 0;
for (int i = 0; i < arr.length; i++){
if (temp < 0){
temp = arr[i];
} else {
temp += arr[i];
}
res = Math.max(res, temp);
}
return res;
}解析：当前次的排名x(k) = (x(k-1) + m)%n
public int LastRemaining_Solution(int n, int m) {
if (n == 0)return -1;
if (n == 1)return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
解析：当前次的排名x(k) = (x(k-1) + m)%n
public int Add(int num1,int num2) {
while (num2 != 0){
int tmp = num1 ^ num2;
num2 = (num1&num2)<<1;
num1 = tmp;
}
return num1;
}