str.find(sub[, start[, end]])
返回子字符串 sub 在 s[start:end] 切片内被找到的最小索引。 可选参数 start 与 end 会被解读为切片表示法。 如果 sub 未被找到则返回 -1。
str.index(sub[, start[, end]])
类似于 find()，但在找不到子字符串时会引发 ValueError
Python3 代码题解
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not haystack and not needle:
return 0
if needle in haystack:
return haystack.index(needle)
else:
return -1
Source: LeetCode（The title reproduced in this blog is for personal study use only）
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
fast = slow = 1
while fast < n:
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
Source: LeetCode（The title reproduced in this blog is for personal study use only）
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
pairs = {
"}": "{",
"]": "[",
")": "(",
}
stack = list()
for i in s:
if i in pairs:
if not stack or stack[-1] != pairs[i]:
return False
stack.pop()
else:
stack.append(i)
return not stack
Source: LeetCode（The title reproduced in this blog is for personal study use only）
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs:
return ""
prefix, cont = strs[0], len(strs)
for i in range(1, cont):
prefix = self.lcp(prefix, strs[i])
if not prefix:
break
return prefix
def lcp(self, str1, str2):
length, index = min(len(str1), len(str2)), 0
while index < length and str1[index] == str2[index]:
index += 1
return str1[:index]
Source: LeetCode（The title reproduced in this blog is for personal study use only）
int romanToInt(char* s) {
int symbolValues[26];
symbolValues['I' - 'A'] = 1;
symbolValues['V' - 'A'] = 5;
symbolValues['X' - 'A'] = 10;
symbolValues['L' - 'A'] = 50;
symbolValues['C' - 'A'] = 100;
symbolValues['D' - 'A'] = 500;
symbolValues['M' - 'A'] = 1000;
int ans = 0;
int n = strlen(s);
for (int i = 0; i < n; ++i) {
int value = symbolValues[s[i] - 'A'];
if (i < n - 1 && value < symbolValues[s[i + 1] - 'A']) {
ans -= value;
} else {
ans += value;
}
}
return ans;
}
Python3 代码题解
class Solution:
SYMBOL_VALUES = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
def romanToInt(self, s: str) -> int:
ans = 0
n = len(s)
for i, ch in enumerate(s):
value = Solution.SYMBOL_VALUES[ch]
//判断当前字符是否是特殊情况，即当前字符的数值小于下一个字符的数值。如果是特殊情况，需要减去当前字符的数值。
if i < n - 1 and value < Solution.SYMBOL_VALUES[s[i + 1]]:
ans -= value
else:
ans += value
return ans
Source: LeetCode（The title reproduced in this blog is for personal study use only）
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
for (int i = 0; i < numsSize; ++i){
for(int j = i + 1; j < numsSize; ++j){
if (nums[i] + nums[j] == target){
int* ret = malloc(sizeof(int) * 2);
ret[0] = i;
ret[1] = j;
*returnSize = 2;
return ret;
}
}
}
*returnSize = 0;
return NULL;
}
C++ 代码解法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};
Python3 代码解法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i,j]
return []
Java 代码解法
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(nums[0] + nums[1] == target){
return new int[]{i,j};
}
}
}
return new int[0];
}
}
复杂度分析 时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。 空间复杂度：O(1)。
方法二：哈希表
注意到方法一的时间复杂度较高的原因是寻找到 target - x 的时间复杂度过高。因此，我们需要一个更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出他的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1) 。
这样我们创建一个哈希表，对于每一个 x ，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
Python 代码解法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []
Java 代码解法
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
Source: LeetCode（The title reproduced in this blog is for personal study use only）
