# Leetcode

## 正文

### 1. two sum

#### 题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

``````Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
``````

Example 2:

``````Input: nums = [3,2,4], target = 6
Output: [1,2]
``````

Example 3:

``````Input: nums = [3,3], target = 6
Output: [0,1]
``````

Constraints:

``````2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
``````

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

### 2.Remove Duplicates from Sorted Array

#### 题目

Given a sorted array, remove the duplicates in place such that each element appear only once
and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

### 4. Median of Two Sorted Arrays

#### 题目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

``````Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
``````

Example 2:

``````Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
``````

Constraints:

``````nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
``````

### 11. Container With Most Water

#### 题目

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

``````Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
``````

Example 2:

``````Input: height = [1,1]
Output: 1
``````

Constraints:

``````n == height.length
2 <= n <= 105
0 <= height[i] <= 104
``````

#### 学到的东西

``````a[j] > a[i]时， 水的高度不变， 宽减少， 故面积减少
a[j] < a[i]时， 水的高度减少， 宽减少， 故面积减少
``````

### 15. 3Sum

#### 题目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

``````Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
``````

Example 2:

``````Input: nums = []
Output: []
``````

Example 3:

``````Input: nums = [0]
Output: []
``````

Constraints:

``````0 <= nums.length <= 3000
-105 <= nums[i] <= 105
``````

#### 学到的东西

``````sort(nums.begin(), nums.end());//c++可以直接调用sort
vector<vector<int>> ans;  //vector<int>是定义了一个list ，而两个vector可以理解成创建了一个二维数组
if (nums[second] + nums[third] == target) {
//类似于python的list.append ，这里直接输入宽度为3，长度为n的向量。
ans.push_back({nums[first], nums[second], nums[third]});
}
``````

THE END