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