Leetcode 1

Array(Easy)

1. 26 Remove Duplicates from Sorted Array

       利用快慢指针，back 指针从 0 开始，front 指针从 1 开始，如果 back和 front 所指数字相等，就一直后移  。如果不相等，back 指针后移一位用来保存当前 front 所指的值，然后继续回到 front 的后移中去。

 1 class Solution {
 2     public int removeDuplicates(int[] nums) {
 3         int back = 0;
 4         
 5         if( nums.length == 0)
 6             return 0;
 7      
 8         for (int front = 1 ; front < nums.length ; front++){
 9             if( nums[front] != nums[back] ){
10                 back++;
11                 nums[back] = nums[front];
12             }
13         }
14         return back+1;
15     }
16 }

　　时间复杂度： O（n）。

　　空间复杂度：O（1）。

2. 35 Search Insert Position

   二分法

 1 class Solution {
 2     public int searchInsert(int[] nums, int target) {
 3         if ( nums.length == 0)
 4             return 0;
 5         
 6         int left = 0;
 7         int right = nums.length - 1;
 8         
 9         while(left <= right){
10             int mid = (right + left)/2;
11             if(nums[mid] > target)
12                 right = mid-1;
13             else if(nums[mid] < target)
14                 left = mid + 1;
15             else
16                 return mid;
17         }
18         return left;
19     }
20 }

3. 53 Maximum Subarray

　　动态规划: 

　　用一个一维数组 dp [ i ] 表示以下标 i 结尾的子数组的元素的最大的和，也就是这个子数组最后一个元素是下边为 i 的元素，并且这个子数组是所有以 i 结尾的子数组中，和最大的。

　　这样的话就有两种情况，

• 如果 dp [ i - 1 ] < 0，那么 dp [ i ] = nums [ i ]。
• 如果 dp [ i - 1 ] >= 0，那么 dp [ i ] = dp [ i - 1 ] + nums [ i ]。
• 可优化：dp数组只需用一个变量存储即可。

•  1 class Solution {
   2     public int maxSubArray(int[] nums) {
   3         int n = nums.length;
   4         int max = nums[0];
   5         int dp = nums[0];
   6        
   7         for( int i = 1; i < n ; i++){
   8             if(dp < 0)
   9                 dp = nums[i];
  10             else
  11                 dp = dp + nums[i];
  12             max = Math.max( dp, max);
  13         }
  14         
  15         return max;
  16     }
  17 }