\chapter{Array}

\section{Two Sum} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

\textbf{Example:}

Given nums = \code{[2, 7, 11, 15]}, target = 9,

Because \code{nums[0] + nums[1] = 2 + 7 = 9},

return \code{[0, 1]}.

\subsubsection{Solution}

\begin{Code}

/**

* 如果符合条件的不止一组呢？则找到一组就从map删除一组

* 另外要考虑的case如[3,3], 6，即存在相同数的情况

*/

public int[] twoSum(int[] nums, int target) {

HashMap<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

map.put(nums[i], i);

}

for (int i = 0; i < nums.length; i++) {

Integer index = map.get(target - nums[i]);

if (index != null && index != i) {

return new int[] {

i, index

};

}

}

return null;

}

\end{Code}

\section{Two Sum II - Input array is sorted} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

\textbf{Input:} numbers=\code{{2, 7, 11, 15}}, target=9

\textbf{Output:} index1=1, index2=2

\subsubsection{Solution}

\begin{Code}

public int[] twoSum(int[] numbers, int target) {

for (int i = 0, j = numbers.length - 1; i < j; ) {

int sum = numbers[i] + numbers[j];

if (sum > target) {

j--;

} else if (sum < target) {

i++;

} else {

return new int[] {i + 1, j + 1};

}

}

return null;

}

\end{Code}

\section{Two Sum III - Data structure design} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.

find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

\begin{Code}

add(1); add(3); add(5);

find(4) -> true

find(7) -> false

\end{Code}

\subsubsection{Solution}

\begin{Code}

private HashMap<Integer, Integer> mMap;

public TwoSumIII() {

mMap = new HashMap<>();

}

/** Add the number to an internal data structure.. */

public void add(int number) {

mMap.put(number, mMap.getOrDefault(number, 0) + 1);

}

/** Find if there exists any pair of numbers which sum is equal to the value. */

public boolean find(int value) {

for (Integer n : mMap.keySet()) {

int cnt = mMap.getOrDefault(value - n, 0);

if (value - n != n && cnt > 0) {

return true;

}

if (value - n == n && cnt > 1) {

return true;

}

}

return false;

}

\end{Code}

\section{Two Sum IV - Input is a BST} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

\textbf{Example 1:}

\textbf{Input:}

\begin{Code}

5

/ \

3 6

/ \ \

2 4 7

\end{Code}

Target = 9

\textbf{Output:} True

\textbf{Example 2:}

\textbf{Input:}

\begin{Code}

5

/ \

3 6

/ \ \

2 4 7

\end{Code}

Target = 28

\textbf{Output:} False

\subsubsection{Solution}

\begin{Code}

public boolean findTarget(TreeNode root, int k) {

List<Integer> nums = new ArrayList<>();

inorder(root, nums);

for (int i = 0, j = nums.size() - 1; i < j; ) {

if (nums.get(i) + nums.get(j) == k) return true;

if (nums.get(i) + nums.get(j) < k) i++;

else j--;

}

return false;

}

public void inorder(TreeNode root, List<Integer> nums) {

if (root == null) return;

inorder(root.left, nums);

nums.add(root.val);

inorder(root.right, nums);

}

\end{Code}

\section{3Sum} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = \code{[-1, 0, 1, 2, -1, -4]},

A solution set is:

\begin{Code}

[

[-1, 0, 1],

[-1, -1, 2]

]

\end{Code}

\subsubsection{Solution}

\begin{Code}

// 耗时30ms

public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);

List<List<Integer>> result = new LinkedList<>();

for (int i = 0; i < nums.length; i++) {

if (i > 0 && nums[i] == nums[i - 1]) {

continue;

}

for (int j = i + 1, k = nums.length - 1; j < k; ) {

int sum = nums[i] + nums[j] + nums[k];

if (sum > 0) {

k--;

} else if (sum < 0) {

j++;

} else {

result.add(Arrays.asList(nums[i], nums[j], nums[k]));

for (j++, k--; j < k && nums[j] == nums[j - 1]; j++);

}

}

}

return result;

}

\end{Code}

\section{3Sum Closest} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = \code{{-1 2 1 -4}}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

\subsubsection{Solution}

\begin{Code}

public int threeSumClosest(int[] nums, int target) {

Arrays.sort(nums);

long dis = Integer.MAX_VALUE, result = 0;

for (int i = 0; i < nums.length - 2; i++) {

int newTarget = target - nums[i];

for (int j = i + 1, k = nums.length - 1; j < k; ) {

int sum = nums[j] + nums[k];

if (sum > newTarget) {

k--;

} else if (sum < newTarget) {

j++;

} else {

return target;

}

long delta = Math.abs(newTarget - sum);

if (delta < dis) {

dis = delta;

result = sum + nums[i];

}

}

}

return (int) result;

}

\end{Code}

\section{3Sum Smaller} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = \code{[-2, 0, 1, 3]}, and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

\begin{Code}

[-2, 0, 1]

[-2, 0, 3]

\end{Code}

\textbf{Follow up:}

Could you solve it in O(n2) runtime?

\subsubsection{Solution}

\begin{Code}

/**

* 注意这里别画蛇添足的加上

* if (nums[i] > target) {

* break;

* }

* 虽然后面的数大于等于nums[i]，但是有可能是负数，三个数之和还是可能小于target的

*/

public int threeSumSmaller(int[] nums, int target) {

Arrays.sort(nums);

int count = 0;

for (int i = 0; i < nums.length - 2; i++) {

for (int j = i + 1, k = nums.length - 1; j < k; ) {

if (nums[i] + nums[j] + nums[k] >= target) {

k--;

} else {

count += k - j;

j++;

}

}

}

return count;

}

\end{Code}

\section{Median of Two Sorted Arrays} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

\textbf{Example 1:}

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

\textbf{Example 2:}

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

\subsubsection{Solution}

\begin{Code}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int len1 = nums1.length;

int len2 = nums2.length;

int total = len1 + len2;

if ((total & 1) != 0) {

return findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, total / 2 + 1);

} else {

return (findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, total / 2) + findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, total / 2 + 1)) / 2.0f;

}

}

private double findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {

int len1 = end1 - start1 + 1;

int len2 = end2 - start2 + 1;

if (len1 > len2) {

return findKth(nums2, start2, end2, nums1, start1, end1, k);

} else if (len1 == 0) {

return nums2[k - 1];

} else if (k == 1) {

return Math.min(nums1[start1], nums2[start2]);

}

int ia = Math.min(k / 2, len1), ib = k - ia;

if (nums1[start1 + ia - 1] > nums2[start2 + ib - 1]) {

return findKth(nums1, start1, end1, nums2, start2 + ib, end2, k - ib);

} else if (nums1[start1 + ia - 1] < nums2[start2 + ib - 1]) {

return findKth(nums1, start1 + ia, end1, nums2, start2, end2, k - ia);

} else {

return nums1[start1 + ia - 1];

}

}

\end{Code}

\section{Move Zeroes} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

\textbf{Note:}

You must do this in-place without making a copy of the array.

Minimize the total number of operations.

\subsubsection{Solution}

\begin{Code}

public void moveZeroes(int[] nums) {

for (int i = 0, j = 0; j < nums.length; j++) {

if (nums[j] != 0) {

swap(nums, i++, j);

}

}

}

private void swap(int[] nums, int i, int j) {

int t = nums[i];

nums[i] = nums[j];

nums[j] = t;

}

/**

* 要求操作次数最少，如果不要求保持顺序，无需理会超出的部分，所以这里不用swap，

* 另外当i==j时就不要多余地操作一次了，最后返回有效部分的长度

*/

public int moveZeroes2(int[] nums) {

int i = 0, j = nums.length - 1;

while (i <= j) {

if (nums[i] != 0) {

i++;

} else if (nums[j] == 0) {

j--;

} else {

if (i != j) {

nums[i] = nums[j];

}

i++;

j--;

}

}

return i;

}

\end{Code}

\section{Plus One} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

\subsubsection{Solution}

\begin{Code}

public int[] plusOne(int[] digits) {

for (int i = digits.length - 1; i >= 0; i--) {

if (digits[i] < 9) {

digits[i]++;

return digits;

}

digits[i] = 0;

}

int[] res = new int[digits.length + 1];

res[0] = 1;

return res;

}

\end{Code}

\section{Container With Most Water} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

\textbf{Note:} You may not slant the container and n is at least 2.

\subsubsection{Analysis}

本体可用暴力法，但显然会超时

一种O(n)的方法是对于区间[left, right]，假如height[left] < height[right]，则我们可以认定[left, right - 1]，[left, right - 2] ...

都不会比[left, right]装的水更多。原因是假如height[right - 1]比height[left]高，则水平面高度不变，但宽度减小了。假如height[right - 1]比height[left]矮，则一样装的水会更少。所以对于一个区间，我们总是从矮的一方往前递进。

\subsubsection{Solution}

\begin{Code}

public int maxArea(int[] height) {

int max = 0;

for (int left = 0, right = height.length - 1; left < right; ) {

max = Math.max(max, Math.min(height[left], height[right]) * (right - left));

if (height[left] < height[right]) {

left++;

} else {

right--;

}

}

return max;

}

\end{Code}

\section{Contains Duplicate} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

\subsubsection{Solution}

\begin{Code}

public boolean containsDuplicate(int[] nums) {

Set<Integer> set = new HashSet<Integer>();

for (int n : nums) {

if (set.contains(n)) {

return true;

}

set.add(n);

}

return false;

}

\end{Code}

\section{Contains Duplicate II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

\subsubsection{Solution I}

\begin{Code}

public boolean containsNearbyDuplicate(int[] nums, int k) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

for (int i = 0; i < nums.length; i++) {

if (map.containsKey(nums[i])) {

if (i - map.get(nums[i]) <= k) {

return true;

}

}

map.put(nums[i], i);

}

return false;

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

public boolean containsNearbyDuplicate2(int[] nums, int k) {

Set<Integer> set = new HashSet<Integer>();

for (int i = 0; i < nums.length; i++) {

if (i >= k + 1) {

set.remove(nums[i - k - 1]);

}

if (set.contains(nums[i])) {

return true;

}

set.add(nums[i]);

}

return false;

}

\end{Code}

\section{Contains Duplicate III} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

\subsubsection{Solution}

\begin{Code}

/**

* 这题关键要注意溢出的问题

* TestCase

* [-1, 2147483647], k = 1, t = 2147483647

*/

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

if (k < 1 || t < 0) {

return false;

}

Map<Long, Integer> map = new HashMap<Long, Integer>();

for (int i = 0; i < nums.length; i++) {

long index = ((long) nums[i] - Integer.MIN_VALUE) / ((long) t + 1);

if (map.containsKey(index) ||

(map.containsKey(index - 1) && (long) nums[i] - map.get(index - 1) <= t)

|| (map.containsKey(index + 1) && map.get(index + 1) - (long) nums[i] <= t)) {

return true;

}

if (map.size() >= k) {

long index1 = ((long) nums[i - k] - Integer.MIN_VALUE) / (t + 1);

map.remove(index1);

}

map.put(index, nums[i]);

}

return false;

}

\end{Code}

\section{Trapping Rain Water} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

\begin{center}

\includegraphics[width=100pt]{water.png}\\

\end{center}

\subsubsection{Analysis}

核心思路就是对于每根柱子，找到其左边最高的柱子和右边最高的柱子，构成一个桶，形成一个水平面，然后对该柱子形成的高度差就是能装的水

\subsubsection{Solution}

\begin{Code}

// 耗时24ms

public int trap(int[] height) {

int len = height.length;

if (len == 0) {

return 0;

}

int[] left = new int[len];

int[] right = new int[len];

left[0] = 0;

right[len - 1] = 0;

for (int i = 1; i < len; i++) {

left[i] = Math.max(left[i - 1], height[i - 1]);

}

for (int i = len - 2; i>= 0; i--) {

right[i] = Math.max(right[i + 1], height[i + 1]);

}

int sum = 0;

for (int i = 0; i < len; i++) {

int high = Math.min(left[i], right[i]);

if (high > height[i]) {

sum += high - height[i];

}

}

return sum;

}

\end{Code}

\section{Trapping Rain Water II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

\textbf{Note:}

Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

\textbf{Example:}

Given the following 3x6 height map:

\begin{Code}

[

[1,4,3,1,3,2],

[3,2,1,3,2,4],

[2,3,3,2,3,1]

]

\end{Code}

Return 4.

\begin{center}

\includegraphics[width=150pt]{water2.png}\\

\end{center}

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

\begin{center}

\includegraphics[width=150pt]{water3.png}\\

\end{center}

After the rain, water are trapped between the blocks. The total volume of water trapped is 4.

\subsubsection{Analysis}

思路是从外围开始，选择最短的柱子，以该柱子为标准，计算其四周的柱子所能容纳的水，并且更新四周柱子的高度，并加到小堆中。为什么这样呢？一个柱子所能蓄的水和该柱子相邻的四根柱子有关，所以我们从边界开始，不断向中间靠拢，每次都取队列中最短的那根柱子计算

\subsubsection{Solution}

\begin{Code}

public int trapRainWater(int[][] heightMap) {

if (heightMap.length == 0) {

return 0;

}

Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

@Override

public int compare(int[] o1, int[] o2) {

return o1[2] - o2[2];

}

});

int row = heightMap.length, col = heightMap[0].length;

boolean[][] visited = new boolean[row][col];

for (int i = 0; i < col; i++) {

queue.add(new int[] {0, i, heightMap[0][i]});

queue.add(new int[] {row - 1, i, heightMap[row - 1][i]});

visited[0][i] = true;

visited[row - 1][i] = true;

}

for (int i = 0; i < row; i++) {

queue.add(new int[] {i, 0, heightMap[i][0]});

queue.add(new int[] {i, col - 1, heightMap[i][col - 1]});

visited[i][0] = true;

visited[i][col - 1] = true;

}

int res = 0;

int[][] delta = new int[][] {

{-1, 0}, {1, 0}, {0, -1}, {0, 1}

};

while (!queue.isEmpty()) {

int[] node = queue.poll();

int x = node[0], y = node[1], z = node[2];

for (int i = 0; i < delta.length; i++) {

int xx = x + delta[i][0], yy = y + delta[i][1];

if (xx >= 0 && xx < row && yy >= 0 && yy < col && !visited[xx][yy]) {

visited[xx][yy] = true;

res += Math.max(0, z - heightMap[xx][yy]);

/**

* 这里要更新柱子的高度，因为水平面肯定是Math.max(z, heightMap[xx][yy])

*/

queue.add(new int[] {xx, yy, Math.max(z, heightMap[xx][yy])});

}

}

}

return res;

}

\end{Code}

\section{Product of Array Except Self} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

\textbf{Follow up:}

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

\subsubsection{Solution}

\begin{Code}

public int[] productExceptSelf(int[] nums) {

if (nums.length == 0) {

return null;

}

int[] result = new int[nums.length];

result[0] = 1;

for (int i = 1; i < nums.length; i++) {

result[i] = nums[i - 1] * result[i - 1];

}

int right = 1;

for (int i = nums.length - 1; i >= 0; i--) {

result[i] *= right;

right *= nums[i];

}

return result;

}

\end{Code}

\section{Find Minimum in Rotated Sorted Array} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

\subsubsection{Solution}

\begin{Code}

public int findMin(int[] nums) {

for (int left = 0, right = nums.length - 1; left >= 0 && left <= right; ) {

if (nums[right] > nums[left]) {

return nums[left];

}

int mid = left + ((right - left) >> 1);

if (nums[mid] > nums[left]) {

left = mid + 1;

} else if (nums[mid] < nums[right]) {

right = mid;

} else {

return Math.min(nums[left], nums[right]);

}

}

return 0;

}

\end{Code}

\section{Find Minimum in Rotated Sorted Array II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Follow up for "Find Minimum in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

\subsubsection{Solution}

\begin{Code}

public int findMin(int[] nums) {

int left = 0, right = nums.length - 1;

for ( ; left < right; ) {

int mid = left + ((right - left) >> 1);

if (nums[right] > nums[left]) {

return nums[left];

}

if (nums[mid] > nums[left]) {

left = mid + 1;

} else if (nums[mid] < nums[right]) {

right = mid;

} else {

left++;

}

}

return nums[left];

}

\end{Code}

\section{Search in Rotated Sorted Array} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

\subsubsection{Solution}

\begin{Code}

public int search(int[] nums, int target) {

int left = 0, right = nums.length - 1;

// 注意这里的等号

while (left <= right) {

int mid = left + ((right - left) >>> 1);

if (target == nums[mid]) {

return mid;

}

// 注意这里的等号

// 先确定单调区间，然后判断target是不是在单调区间内，如果不在就在另一半区间

if (nums[mid] >= nums[left]) {

if (target >= nums[left] && target < nums[mid]) {

right = mid - 1;

} else {

left = mid + 1;

}

} else if (nums[mid] < nums[right]) {

if (target > nums[mid] && target <= nums[right]) {

left = mid + 1;

} else {

right = mid - 1;

}

}

}

return -1;

}

\end{Code}

\section{Search in Rotated Sorted Array II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Follow up for "Search in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

\subsubsection{Solution}

\begin{Code}

public int search(int[] nums, int target) {

int left = 0, right = nums.length - 1;

// 注意这里的等号

while (left <= right) {

int mid = left + ((right - left) >>> 1);

if (target == nums[mid]) {

return mid;

}

// 注意这里的等号

// 先确定单调区间，然后判断target是不是在单调区间内，如果不在就在另一半区间

if (nums[mid] > nums[left]) {

if (target >= nums[left] && target < nums[mid]) {

right = mid - 1;

} else {

left = mid + 1;

}

} else if (nums[mid] == nums[left]) {

// nums[mid]==nums[left]有两种情况，在不好确定哪种情况时，left++可以进一步缩小范围

left++;

} else {

// 这里可以肯定nums[mid]<nums[left]，所以mid肯定在拐点右边，换言之右边是单调的

if (target > nums[mid] && target <= nums[right]) {

left = mid + 1;

} else {

right = mid - 1;

}

}

}

return -1;

}

\end{Code}

\section{Pascal's Triangle} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Return

\begin{Code}

[

[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

\end{Code}

\subsubsection{Solution}

\begin{Code}

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> allrows = new ArrayList<>();

ArrayList<Integer> row = new ArrayList<>();

for (int i = 0; i < numRows; i++) {

row.add(0, 1);

for (int j = 1; j < row.size() - 1; j++)

row.set(j, row.get(j) + row.get(j + 1));

allrows.add(new ArrayList<>(row));

}

return allrows;

}

\end{Code}

\section{Pascal's Triangle II} %%%%%%%%%%%%%%%%%%%%%%