原题

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].

UPDATE (2016/2/13):
The return format had been changed to zero-based indices.
Please read the above updated description carefully.

原题

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].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

先介绍下背景，刚来美国3个月，英语不溜只会点菜那种，无驾照，无SSN，无工作，F1签证。

一般有美国签证申请英国签证是不会被拒签的，除非你的材料有大问题，所以认真准备都是可以过的

去英国玩是个很仓促的决定，所以我是提前一个月才开始申请的，请不要学我，一般要提前三个月

原题

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路

非常典型的DP问题。

子数组只会有两种操作：

1. 如果总和比之前大就不停的添加新成员
2. 如果总和比之前一次变小了就清空成员重新计数

于是只用记住历史最大值和数组总和最大值就好

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxValue = INT_MIN;
        int tempMax = 0;
        for(int x:nums){
            tempMax = max(tempMax + x,x);
            maxValue = max(maxValue,tempMax);
        }
        return maxValue;
    }
    
};

题目

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0