【LeetCode-面试经典150题-day7】

392.判断子序列

题意：

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

【输入样例】

s="abc",t="ahbgdc"

【输出样例】true

解题思路：

双指针枚举

class Solution {public boolean isSubsequence(String s, String t) {//双指针int i=0,j=0;while(i < s.length() && j < t.length()){if(s.charAt(i) == t.charAt(j)){//相等了，指针往后++i;++j;}else{//相等的情况下只移动j++j;}}if(i == s.length()){return true;}else{return false;}}
}

时间： 击败了88.73%

内存： 击败了86.35%

 167.两数之和Ⅱ-输入有序数组

题意：

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间

【输入样例】

numbers=[2,7,11,15],target=9

【输出样例】[1,2]

解题思路：

双指针枚举,一个从前开始往后走（i）,一个从后往前走(j)。

题目说，对应一个唯一的答案，且i<j

两者往中间靠拢，当numbers[i]+numbers[j]>target时，由于numbers[i]是较小值，所以太大了要减少较大值，--j,同理当小于target时，要增加较小值；

注意下标从1开始，所以赋值给ans数组时下标都要+1.

 

class Solution {public int[] twoSum(int[] numbers, int target) {//下标从1开始噢//双指针i，j 如果i+j小于target，增加i//如果i+j大于target，减少jint[] ans= new int[2];int i=0,j=numbers.length - 1;while(i<j){//不会相等，所以i<jif(numbers[i] + numbers[j] == target){ans[0] = i+1;ans[1] = j+1;return ans;}if(numbers[i] + numbers[j] < target){++i;}if(numbers[i] + numbers[j] > target){--j;}}return ans;}
}

时间： 击败了98.30%

内存：击败了75.64%