# Two Pointers

## 42. Trapping Rain Water 收集雨水

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. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 解法1 这道题给出一个数组,每个元素是一个宽为1的bar,问这些bar组成的图行最多能装多少水,就是图上蓝色的部分.如果当前位置高度大于两边的高度,我们就认为当前位置对结果有贡献.当前位置的贡献值,为左边高度的最大值和右边高度的最大值,取其中最小的和当前的高度相减. class Solution { public: int trap(vector<int>& height) { int l=0,r=height.size()-1,level=0,water=0; while(l < r){ int lower = height[height[l]<height[r]?

## 30. Substring With Concatenation of All Words 串联所有单词的子串

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. For example, given: s: "barfoothefoobarman" words: ["foo", "bar"] You should return the indices: [0,9]. (order does not matter). Difficulty: Hard 这道题让我们求串联所有单词的子串.所有单词来自输入的数组.所有单词的长度一样,串联的顺序不一定.如题中的例子,可以串联成foobar, barfoo. 这里我们用两个哈希表,一个用来存输入单词数组的每个单词和其的出现次数.然后遍历输入的字符串.设单词的个数为n,每个单词长度为m.每次遍历检查母字符串从该位置开始,每m截取一下查看在第一个哈希表是否存在.如果存在,存入第二个哈希表.如果n个次截取都匹配则这次遍历是符合要求的,存一下结果. 解法1 就是上面分析 class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int>res; if (s.

## 28. Implement strStr() 实现strStr()函数

Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1 Difficulty: Easy 这道题让我们找出字符串中某个子字符串第一次出现的index.如果子字符串的长度为0,则返回0,如果子字符传的长度大于母字符串,则返回-1.遍历字符串的时候只需要遍历到剩下的长度等于字符串的位置即可. class Solution { public: int strStr(string haystack, string needle) { if (needle.empty()) return 0; int m = haystack.size(),n=needle.size(); if (m<n) return -1; for (int i=0;i<=m-n;++i) { int j=0; for (j=0;j<n;j++) if (haystack[i+j]!

## 27. Remove Element 移除元素

Given an array and a value, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example: Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2.

## 26. 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 by modifying the input array in-place with O(1) extra memory. Example: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

## 19. Remove Nth Node From End of List 移除链表倒数第N个节点

Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass. Difficulty: Medium 这道题让我们溢出链表中第N个节点,并制定n为有效的,就是n不会大于链表元素的总个数.看网上说这道题在问的时候可能会加上限制在一次循环的条件完成.如果用一次循环完成的话,就不能单独用一次循环来求链表元素的个数,要在循环到要删除的元素的位置时就该删除该元素.所以需要一点技巧. 我们可以定义两个指针pre,cur.先让cur前进N步,如果此时cur指向的为NULL,说明该链表的长度为N,所以移除首个元素就可以.如果cur指向的不为NULL,那么此时同时让pre,cur同时前进,直到cur指向最后一个元素,此时pre指向的就是倒数第N个元素,删除即可. 剑指offer 56题与这道题稍微有点像,可以一起看下 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (!

## 18. 4Sum 四数之和

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] Difficulty: Medium

## 16. 3Sum Closest 最近三数之和

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 = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

## 15. 3Sum 三数之和

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 = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 这道题比Two Sum 两数之和等于一个输入的数复杂一些.

## 11. Container With Most Water 装最多水的容器

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. Note: You may not slant the container and n is at least 2. Difficulty: Medium

## Longest Substring Without Repeating Characters 子字符串的最大不重复长度

Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. 滑动窗口问题,比如abcabcbb,滑动到abca的时候需要丢弃第一个a变成bca,继续向右滑动,每次滑动都要检查有没有重复.感觉涉及到最大,最多的问题都可以试着网哈希表上靠. class Solution { public: int lengthOfLongestSubstring(string s) { int size = s.