• 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). 123     For example, given array S = {-1 2 1 -4}, and target = ……
  • 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: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) 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) 12345   &nb……
  • Two Sum

    问题描述: 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. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 1234 Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1]. UPDATE (2016/2/13): Th……
  • Longest Consecutive Sequence

    问题描述: Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity. 题解: 分析: 如果允许O(nlogn)的复杂度,那么可以先排序,可是本题要求O(n)。 由于序列里的元素是无序的,又要求O(n),首先要想到用哈希表。 用一个哈希表unordered)map<int, bool>记录每个元素是否使用,对每个元素,以该元素……
  • Search in Rotated Sorted Array II

    问题描述: Follow up for ”Search in Rotated Sorted Array”: What ifduplicatesare allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. 题解: 分析:与”Search in Rotated Sorted Array”的区别在于数组中允许相同的元素存在。那么对于若A[m] >= A[l],则有[l,m]为递增序列的假设不成立。比如[1,3,1,1,1]。 所以,对于出现边界相等的情况,我们需要特殊处理。为此,我们可以将A[m] >= A[l]拆分为两个条件: 1)如果A[m] > A[l],则区间[l……
  • Search in Rotated Sorted Array

    问题描述: Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e.,0 1 2 4 5 6 7might become4 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. 题解: 二分查找,需要注意左右边界的确定。 C++实现: //时间复杂度O(logn),空间复杂度O(1) class Solution { public: int search(vector<int>& nums, int target) { int first = 0, las……
  • Remove Duplicates from Sorted Array II

    问题描述: Follow up for "Remove Duplicates": What if duplicates are allowed at most twice? For example, Given sorted array nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length. 题解: 分析:与上一个题目类似,定义一个游标变量index,初始值指向数组第三个(下标为2)元素,然后从数组第三个元素开始遍历数组,并依次比较第i个元素与第i-2个元素是否相等。如果相等,则说明当前的第i个元……
  • 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]. 题解: 分析:定义一个游标变量,初始值指向数组第一个元素,然后从数组第二个元素开始遍历数组,如果遍历到的原始值与当前游标所指示的值不相同,则将游标往后移动。最终游标值加1……