题目一
原题链接 https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [, , , ], target = 因为 nums[] + nums[] = + =
所以返回 [, ]
提示：不能自身相加。
测试用例
[,,,]
预期结果
[,]
格式模板
public class Solution {
public int[] TwoSum(int[] nums, int target) {
/*
代码
*/
}
}
笔者的代码，仅供参考
使用暴力方法，运行时间 700ms-1100ms
public class Solution {
public int[] TwoSum(int[] nums, int target) {
int [] a = new int[];
for (int i = ; i < nums.Length - ; i++)
{
for (int j = i + ; j < nums.Length; j++)
{
if (nums[i] + nums[j] == target)
{
a[] = i;
a[] = j;
}
}
}
return a;
}
}
运行时间 400ms-600ms
由于使用的是哈希表，所以缺点是键不能相同。
public class Solution {
public int[] TwoSum(int[] nums, int target) {
int[] a = new int[];
System.Collections.Hashtable hashtable = new System.Collections.Hashtable();
for(int i = ; i < nums.Length; i++)
{
hashtable.Add(nums[i], i);
}
for(int i = ; i < nums.Length; i++)
{
int complement = target - nums[i];
if (hashtable.ContainsKey(complement) && int.Parse(hashtable[complement].ToString())!=i)
{
a[] = i;
a[] = int.Parse(hashtable[complement].ToString());
}
}
return a;
}
}
还是哈希表，缺点是哈希表存储的类型是object，获取值时需要进行转换。
public int[] TwoSum(int[] nums, int target)
{
int[] a = new int[];
System.Collections.Hashtable h = new System.Collections.Hashtable();
for (int i = ; i < nums.Length; i++)
{
int c = target - nums[i];
if (h.ContainsKey(c))
{
a[] = int.Parse(h[c].ToString()) <= nums[i] ? int.Parse(h[c].ToString()) : i;
a[] = int.Parse(h[c].ToString()) > nums[i] ? int.Parse(h[c].ToString()) : i;
}
else if (!h.ContainsKey(nums[i]))
{
h.Add(nums[i], i);
}
}
return a;
}
抄一下别人的
public class Solution
{
public int[] TwoSum(int[] nums, int target)
{
int[] res = {, };
int len = nums.Length;
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = ; i < len; i++)
{
int query = target - nums[i];
if (dict.ContainsKey(query))
{
int min = (i <= dict[query]) ? i : dict[query];
int max = (i <= dict[query]) ? dict[query] : i;
return new int[] { min, max };
}
else if (!dict.ContainsKey(nums[i]))
{
dict.Add(nums[i], i);
}
} return res;
}
}
---------------------
作者：Bruce-Yeung
来源：CSDN
原文：https://blog.csdn.net/lzuacm/article/details/80551669
版权声明：本文为博主原创文章，转载请附上博文链接！
题目二
原题地址https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出:
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 。
示例 2:
输入: "bbbbb"
输出:
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 。
示例 3:
输入: "pwwkew"
输出:
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 。
要注意字符串为空、变量为null、字符串长度 Length = 1 等情况。
测试实例
输入
" "
"au"
"abcabcbb"
"bbbbb"
"pwwkew"
"aab" 预期结果分别是 1,2,3,1,3,2
代码格式模板
public class Solution {
public int LengthOfLongestSubstring(string s) {
}
}
笔者的代码仅供参考
使用最笨的方式，200ms左右
public class Solution {
public int LengthOfLongestSubstring(string s) {
if (s == null || s == "")
return ;
char[] a = s.ToCharArray(); //字符串转为字符数组
int start = ; //区间开始位置
int stop = ; //区间结束位置
int newMax = ; //当前区间数
int max = ; //区间最大个数
for (stop = ; stop < a.Length; stop++) //每次向后移动一位
{
bool b = false; //是否存在重复
for (int i = start; i < stop; i++) //检查当前元素在区间是否有相同值
{
if (a[stop] == a[i]) //如果stop+1位在区间找到相同的字符
{
char ls = a[stop];
if (newMax > max) max = newMax;
start = i + ; //区间开始位置重置
newMax = stop - start + ;
b = true;
break;
}
}
if (b == false)
newMax += ;
}
if (newMax > max) max = newMax;
return max;
}
}
完整测试代码(控制台)
using System; namespace ConsoleApp1
{
public class Testa
{
public int LengthOfLongestSubstring(string s)
{
if (s == null || s == "")
return ; char[] a = s.ToCharArray(); //字符串转为字符数组
int start = ; //区间开始位置
int stop = ; //区间结束位置
int newMax = ; //当前区间数
int max = ; //区间最大个数 for (stop = ; stop < a.Length; stop++) //每次向后移动一位
{
bool b = false; //是否存在重复
for (int i = start; i < stop; i++) //检查当前元素在区间是否有相同值
{
if (a[stop] == a[i]) //如果stop+1位在区间找到相同的字符
{
char ls = a[stop];
if (newMax > max) max = newMax;
start = i + ; //区间开始位置重置
newMax = stop - start + ; //重新设置区间数
b = true;
break;
}
}
if (b == false) ////没有重新设置区间数时加1
newMax += ;
}
if (newMax > max) max = newMax;
return max;
}
}
class Program
{ static void Main(string[] args)
{
Testa t1 = new Testa(); //正确结果
Console.WriteLine(t1.LengthOfLongestSubstring(" ")); //
Console.WriteLine(t1.LengthOfLongestSubstring("au")); //
Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //
Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb")); //
Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew")); //
Console.WriteLine(t1.LengthOfLongestSubstring("aab")); //
Console.ReadKey();
}
}
}
使用哈希集合，速度更快，100ms-150ms
public int LengthOfLongestSubstring(string s)
{
int n = s.Length;
HashSet<char> set = new HashSet<char>(); //集合
int ans = , start = , stop = ; //ans为字符串长度，starp区间起点，stop区间终点
while (start < n && stop < n)
{
// try to extend the range [i, j]
if (!set.Contains(s[stop]))
{
set.Add(s[stop++]);
ans = Math.Max(ans, stop - start);
//或者ans = ans > (stop - start) ? ans : (stop - start)
}
else
{
set.Remove(s[start++]);
}
}
return ans;
}
完整控制台测试代码
using System;
using System.Collections.Generic;
using System.Linq; namespace ConsoleApp2
{
public class Solution
{
public int LengthOfLongestSubstring(string s)
{
int n = s.Length;
HashSet<char> set = new HashSet<char>(); //集合
int ans = , start = , stop = ; //ans为字符串长度，starp区间起点，stop区间终点
while (start < n && stop < n)
{
// try to extend the range [i, j]
if (!set.Contains(s[stop]))
{
set.Add(s[stop++]);
ans = Math.Max(ans, stop - start);
//或者ans = ans > (stop - start) ? ans : (stop - start)
}
else
{
set.Remove(s[start++]);
}
}
return ans;
}
}
class Program
{
static void Main(string[] args)
{ Solution t1 = new Solution(); //正确结果
Console.WriteLine(t1.LengthOfLongestSubstring(" ")); //
Console.WriteLine(t1.LengthOfLongestSubstring("au")); //
Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //
Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb")); //
Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew")); //
Console.WriteLine(t1.LengthOfLongestSubstring("aab")); //
Console.ReadKey();
}
}
}