## Two Sum

### Original

Question [EASY] 找到两个数， 其和为指定数量。 Given an array of integers, 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.

Hashmap特别要注意的地方就是对于duplicates的考虑， 题目究竟是返回true or false就可以了， 还是需要返回所有符合的index， 还是只是最小（或最大）的index， 都会有不同的实现方案。

### Tricks

Question [EASY]合并两个sorted array变成一个sorted array。 Given two sorted arrays A and B, each having length N and M respectively. Form a new sorted merged array having values of both the arrays in sorted format.

Question [EASY]一次循环找到链表的中间元素。How to find middle element of linked list in one pass?

Question [EASY]判断一个链表是否存在环。 How to find if linked list has a loop ?

Question [EASY]找到链表中倒数第三个元素。How to find 3rd element from end in a linked list in one pass?

### Example1 - continuous maximum subarray

Question [MEDIUM]找到不大于M的连续最大和子数列。 Given an array having N positive integers, find the contiguous subarray having sum as great as possible,, but not greater than M.

### Example2 - continuous minimum distinct subarray

Question [MEDIUM]找到至少含有K个不同数字的连续最小和子数列。 Given an array containing N integers, you need to find the length of the smallest contiguous subarray that contains atleast K distinct elements in it. Output “−1−1” if no such subarray exists.

### Example3 - minimum hustle subsequence

Question [MEDIUM] 找到K个给出最小hustle值的子数列， 不要求连续。 Given an array having N integers, you need to find out a subsequence of K integers such that these K integers have the minimum hustle. Hustle of a sequence is defined as sum of pair-wise absolute differences divided by the number of pairs.

### Example4 - Google phone interview

Question [EASY] 找到number X满足最大cover。Given a set S of 10^6 doubles. Find a number X so that the [X, X+1) half-open real interval contains as many elements of S as possible.For example, given this subset:[2.7, 0.23, 8.32, 9.65, -6.55, 1.55, 1.98, 7.11, 0.49, 2.75, 2.95, -96.023, 0.14, 8.60], the value X desired is 1.98 because there are 4 values in the range 1.98 to 2.97999 (1.98, 2.7, 2.75, 2.95)

### Example5 - three pointers

Question [MEDIUM] 找到最长只含有两个不同字母的子数列长度。 Given a string S, find the length of the longest substring T that contains at most two distinct characters. For example, Given S = “eceba”, T is “ece” which its length is 3.

## Substring

Question [EASY] 查找是否存在子字符串。Implement strstr(). Returns the index of the first occurrence of word1 in word2, or -1 if word1 is not part of word2.

## Reverse Words in String

Question [EASY] 将字符串中的单词们首位调换位置。Reverse words in string. Given an input string s, reverse the string word by word. For example, given s = “the sky is blue”, return “blue is sky the”.

### Tricks

• raw： “ab bc cd”
• target： “cd bc ab”
• reverse each word from raw： “ba cb dc”
• reverse whole string：“cd bc ab”， same as target string.