C# 算法题系列(一) 两数之和、无重复字符的最长子串

内容纲要

题目一

原题链接 https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

提示:不能自身相加。

测试用例

[2,7,11,15]
9
预期结果
[0,1]

格式模板

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[2];
            for (int i = 0; i < nums.Length - 1; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (nums[i] + nums[j] == target)
                    {
                        a[0] = i;
                        a[1] = j;
                    }
                }
            }
            return a;
        }
    }

运行时间 400ms-600ms

由于使用的是哈希表,所以缺点是键不能相同。

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
                     int[] a = new int[2];
            System.Collections.Hashtable hashtable = new System.Collections.Hashtable();
            for(int i = 0; i < nums.Length; i++)
            {
                hashtable.Add(nums[i], i);
            }
            for(int i = 0; i < nums.Length; i++)
            {
                int complement = target - nums[i];
                if (hashtable.ContainsKey(complement) && int.Parse(hashtable[complement].ToString())!=i)
                {
                    a[0] = i;
                    a[1] = int.Parse(hashtable[complement].ToString());
                }
            }
            return a;
        }
    }

 还是哈希表,缺点是哈希表存储的类型是object,获取值时需要进行转换。

        public int[] TwoSum(int[] nums, int target)
        {
            int[] a = new int[2];
            System.Collections.Hashtable h = new System.Collections.Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                int c = target - nums[i];
                if (h.ContainsKey(c))
                {
                    a[0] = int.Parse(h[c].ToString()) <= nums[i] ? int.Parse(h[c].ToString()) : i;
                    a[1] = 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 = {0, 0};
        int len = nums.Length;
        Dictionary<int, int> dict = new Dictionary<int, int>();
        for (int i = 0; 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"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3

要注意字符串为空、变量为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 0;

            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;                       //是否存在重复
                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 + 1;              //区间开始位置重置
                        newMax = stop - start + 1;
                        b = true;            
                        break;
                    }
                }
                if (b == false)
                    newMax += 1;
            }
            if (newMax > max) max = newMax;
            return max;
    }
}

完整测试代码(控制台)

using System;

namespace ConsoleApp1
{
    public class Testa
    {
        public int LengthOfLongestSubstring(string s)
        {
            if (s == null || s == "")
                return 0;

            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;                       //是否存在重复
                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 + 1;              //区间开始位置重置
                        newMax = stop - start + 1;      //重新设置区间数
                        b = true;            
                        break;
                    }
                }
                if (b == false)             ////没有重新设置区间数时加1
                    newMax += 1;
            }
            if (newMax > max) max = newMax;
            return max;
        }
    }
    class Program
    {

        static void Main(string[] args)
        {
            Testa t1 = new Testa();                                     //正确结果
            Console.WriteLine(t1.LengthOfLongestSubstring(" "));        //1
            Console.WriteLine(t1.LengthOfLongestSubstring("au"));       //2
            Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //3
            Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    //1
            Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   //3
            Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      //2
            Console.ReadKey();
        }
    }
}

 

使用哈希集合,速度更快,100ms-150ms

        public int LengthOfLongestSubstring(string s)
        {
            int n = s.Length;
            HashSet<char> set = new HashSet<char>();        //集合
            int ans = 0, start = 0, stop = 0;               //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 = 0, start = 0, stop = 0;               //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(" "));        //1
            Console.WriteLine(t1.LengthOfLongestSubstring("au"));       //2
            Console.WriteLine(t1.LengthOfLongestSubstring("abcabcbb")); //3
            Console.WriteLine(t1.LengthOfLongestSubstring("bbbbb"));    //1
            Console.WriteLine(t1.LengthOfLongestSubstring("pwwkew"));   //3
            Console.WriteLine(t1.LengthOfLongestSubstring("aab"));      //2
            Console.ReadKey();
        }
    }
}

 

点赞
  1. lexapro tablets说道:

    I am also commenting to let you know of the helpful encounter my friend's daughter found reading through your web page. She figured out numerous issues, not to mention what it's like to have an amazing giving mood to have most people really easily know selected impossible subject areas. You really exceeded our own expectations. Many thanks for imparting the invaluable, safe, explanatory and even easy thoughts on the topic to Janet.

发表评论

电子邮件地址不会被公开。 必填项已用*标注